Department of Information Systems

Context-free languages and pushdown automata
Reseach leader:Meduna Alexander
Team members:Čermák Martin, Koutný Jiří, Křivka Zbyněk
Agency:MŠMT
Code:MEB041003
Start:2010
End:2011
Keywords:formal language theory, primitive words, grammars, automata
Annotation:
The planned research will focus on the study of context-free languages and pushdown automata and their applications. To understand the structure of formal languages is a helpful tool to study their combinatorial properties. One of the subjects of this research is the problem of primitive words. A word is called primitive if it is not a power of another word. A widely known conjecture of P. Dömösi, M. Ito, and S. Horváth states that the language Q of all primitive words over an alphabet with several letters is not context-free. A number of recent papers investigated this well-known conjecture which is still open. We intend to continue our investigations on small context-free grammars generating primitive words. On the other hand, using the fact that a homomorphic map of a nonprimitive word is also nonprimitive, we also plan to study whether or not Q has a real Chomsky-Schützenberger-Stanley type homomorphic characterization. By our hope, these investigations may lead to prove or disprove our conjecture. In addition, we would like to characterize context-free languages consisting of non-primitive words. By this research we can also find new important properties of context-free languages.
 
     Studying the combinatorial properties of words and languages we can get  a  lot  of information  on  the  structure  of  languages  in  connection  with the Chomsky hierarchy and corresponding automata. Regarding this subject, one of the most important results is the Bar-Hillel Lemma having an effective method for testing a language whether or not it is context-free. There are some well-known stronger versions of this result. One direction is to study the family of context-free non-linear languages. G. Horváth discovered a strong iteration property of context-free non-linear languages. In this project we would like to continue this line of research. 
 
     By the well-known Chomsky-Schützenberger-Stanley theorem, every context-free language is homomorphically characterized by h and D, R, where h is a homomorphism, D is a Dyck language and R is a regular language. Several extensions of this result are known. In this project we plan to continue this research giving real homomorphic characterizations of context-free languages having certain combinatorial properties (slenderness, poly-slenderness, palindromicity, etc).
 
     The mathematical value of the expected results will be proved by their publications in international scientific journals and conferences.
Accomplishments:
In addition to publications as the main results of this project (see below), we organized 4 public seminars with 6 lectures (all in English) at Faculty of information technology, Brno University of Technology:
  • 29. 3. 2011: J. Falucskai (College of Nyíregyháza, Hungary): Some Algorithms Concerning Uniquely Decipherable Codes; G. Horváth (University of Debrecen, Hungary): Pumping lemmas for linear and nonlinear context-free languages
  • 7. 7. 2011: P. Dömösi (College of Nyíregyháza, Hungary): Context-free languages and primitive words
  • 21. 7. 2011: János Falucskai (College of Nyíregyháza, Hungary): A New Interpretation of the Decipherability
  • 2. 11. 2011: P. Dömösi (College of Nyíregyháza, Hungary): Something About Cryptography; G. Horváth (University of Debrecen, Hungary): The Language of Primitive Words

Publications

2012Čermák Martin, Horáček Petr, Meduna Alexander: Rule-restricted automaton-grammar tranduscers: Power and linguistic applications, In: Mathematics for Applications, Vol. 1, No. 1, 2012, Brno, CZ, p. 13-35, ISSN 1805-3610
 Čermák Martin, Koutný Jiří, Meduna Alexander: Parsing Based on n-Path Tree-Controlled Grammars, In: Theoretical and Applied Informatics, Vol. 2011, No. 23, 2012, Varšava, PL, p. 213-228, ISSN 1896-5334
 Koutný Jiří, Meduna Alexander: Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths, In: Kybernetika, Vol. 48, No. 1, 2012, CZ, p. 165-175, ISSN 0023-5954
 Meduna Alexander, Zemek Petr: One-Sided Forbidding Grammars and Selective Substitution Grammars, In: International Journal of Computer Mathematics, Vol. 89, No. 5, 2012, GB, p. 586-596, ISSN 0020-7160
2011Čermák Martin, Meduna Alexander: n-Accepting Restricted Pushdown Automata Systems, In: 13th International Conference on Automata and Formal Languages, Nyíregyháza, HU, MTA SZTAKI, 2011, p. 168-183, ISBN 978-615-5097-19-5
 Čermák Martin: Basic Properties of n-Languages, In: Proceedings of the 17th Conference and Competition STUDENT EEICT 2011 Volume 3, Brno, CZ, FIT VUT, 2011, p. 460-464, ISBN 978-80-214-4273-3
 Koutný Jiří, Křivka Zbyněk, Meduna Alexander: Pumping Properties of Path-Restricted Tree-Controlled Languages, In: 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Brno, CZ, VUT v Brně, 2011, p. 61-69, ISBN 978-80-214-4305-1
 Koutný Jiří: Syntax Analysis of Tree-Controlled Languages, In: Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3, Brno, CZ, VUT v Brně, 2011, p. 5, ISBN 978-80-214-4273-3
 Křivka Zbyněk, Masopust Tomáš: Cooperating Distributed Grammar Systems with Random Context Grammars as Components, In: Acta Cybernetica, Vol. 20, No. 2, 2011, US, p. 269-283, ISSN 0324-721X
2010Lukáš Roman, Meduna Alexander: Multigenerative Grammar Systems and Matrix Grammars, In: Kybernetika, Vol. 46, No. 1, 2010, CZ, p. 68-82, ISSN 0023-5954

Your IPv4 address: 184.73.74.47
Switch to IPv6 connection

DNSSEC [dnssec]