Algebraic methods in automata and formal language theory
Project goals
The project is aimed to develop algebraic methods in formal language theory. In particular, we will further investigate classes of syntactic structures of regular languages like (ordered) syntactic monoids, syntactic semirings, syntactic homomorphisms, syntactic semirings with the image of the language, etc. with the goal of effectively characterizing membership to important classes of languages. We will also consider the graph structures of the canonical automata. We are going to continue our study ofimplicit language equations. We will mainly concentrate on finding some common factors of different results ensuring regularity of solutions with the aim of formulating a unified theory. We will attempt to develop algorithms for calculating maximal solutions in those cases where they are regular. We will also deal with generalizations of the classical languages of finite words to the so-called tree languages, languages of infinite words and trace languages. Within the project we are going to
Keywords
automataregular languagesvarietiessemiringsinfinite wordstraces
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 9 (SGA02006GA-ST)
Main participants
—
Contest type
VS - Public tender
Contract ID
201/06/0936
Alternative language
Project name in Czech
Algebraické metody v teorii automatů a formálních jazyků
Annotation in Czech
Projekt je zaměřen na rozvoj algebraických metod v teorii formálních jazyků. Zejména budeme dále zkoumat třídy syntaktických struktur regulárních jazyků, jako (uspořádaných) syntaktických monoidů, syntaktických polookruhů, syntaktických homomorfismů, syntaktických polookruhů s obrazem jazyka, atd. s cílem efektivní charakterizace příslušnosti k důležitým třídám jazyků. Budeme též uvažovat grafovou strukturu kanonických automatů. Chystáme se pokračovat v našem studiu implicitních jazykových rovnic. Hlavně se zaměříme na hledání společných rysů různorodých výsledků zajišťujících regularitu řešení s cílem formulace jednotné teorie. Budeme se též věnovat návrhům algoritmů pro výpočet maximálních řešení v těch případech, kdy jsou tato regulární. Též sebudeme zabývat zobecněními klasických jazyků konečných slov na takzvané stromové jazyky, jazyky nekonečných slov a jazyky stop. V rámci projektu budeme pokračovat v naší široké mezinárodní spolupráci. Výsledky budou prezentovány na prestižních
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BA - General mathematics
CEP - secondary branch
IN - Informatics
CEP - another secondary branch
—
10101 - Pure mathematics
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
Our research has concentrated on several areas of theory of formal languages. According to the plan, we have studied syntactic structures of languages, and obtained new results about some important classes of regular languages. We have characterized seve
Solution timeline
Realization period - beginning
Jan 1, 2006
Realization period - end
Dec 31, 2008
Project status
U - Finished project
Latest support payment
Apr 25, 2008
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP09-GA0-GA-U/02:2
Data delivery date
Oct 22, 2009
Finance
Total approved costs
900 thou. CZK
Public financial support
900 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
900 CZK thou.
Public support
900 CZK thou.
100%
Provider
Czech Science Foundation
CEP
BA - General mathematics
Solution period
01. 01. 2006 - 31. 12. 2008