Project Details

Bezkontextové gramatiky a zásobníkové automaty

Project Period: 1. 1. 2010 - 31. 12. 2011

Project Type: grant

Code: MEB041003

Agency: Ministry of Education, Youth and Sports Czech Republic

Program: KONTAKT

English title
Context-free languages and pushdown automata
Type
grant
Keywords

formal language theory, primitive words, grammars, automata

Abstract
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.
Team members
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT) , research leader
Čermák Martin, Ing. (UIFS FIT VUT)
Koutný Jiří, Ing. (UIFS FIT VUT)
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Publications

2012

  • MEDUNA Alexander and ZEMEK Petr. One-Sided Forbidding Grammars and Selective Substitution Grammars. International Journal of Computer Mathematics, vol. 89, no. 5, 2012, pp. 586-596. ISSN 0020-7160. Detail
  • ČERMÁK Martin, HORÁČEK Petr and MEDUNA Alexander. Rule-restricted automaton-grammar transducers: Power and linguistic applications. Mathematics for Applications, vol. 1, no. 1, 2012, pp. 13-35. ISSN 1805-3610. Detail
  • KOUTNÝ Jiří and MEDUNA Alexander. Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths. Kybernetika, vol. 48, no. 1, 2012, pp. 165-175. ISSN 0023-5954. Detail

2011

  • ČERMÁK Martin. Basic Properties of n-Languages. In: Proceedings of the 17th Conference and Competition STUDENT EEICT 2011 Volume 3. Brno: Faculty of Information Technology BUT, 2011, pp. 460-464. ISBN 978-80-214-4273-3. Detail
  • KŘIVKA Zbyněk and MASOPUST Tomáš. Cooperating Distributed Grammar Systems with Random Context Grammars as Components. Acta Cybernetica, vol. 20, no. 2, 2011, pp. 269-283. ISSN 0324-721X. Detail
  • ČERMÁK Martin and MEDUNA Alexander. n-Accepting Restricted Pushdown Automata Systems. In: 13th International Conference on Automata and Formal Languages. Nyíregyháza: Computer and Automation Research Institute, Hungarian Academy of Sciences, 2011, pp. 168-183. ISBN 978-615-5097-19-5. Detail
  • ČERMÁK Martin, KOUTNÝ Jiří and MEDUNA Alexander. Parsing Based on n-Path Tree-Controlled Grammars. Theoretical and Applied Informatics, vol. 23, no. 3, 2011, pp. 213-228. ISSN 1896-5334. Detail
  • KOUTNÝ Jiří, KŘIVKA Zbyněk and MEDUNA Alexander. Pumping Properties of Path-Restricted Tree-Controlled Languages. In: 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Brno University of Technology, 2011, pp. 61-69. ISBN 978-80-214-4305-1. Detail
  • KOUTNÝ Jiří. Syntax Analysis of Tree-Controlled Languages. In: Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3. Brno: Brno University of Technology, 2011, p. 5. ISBN 978-80-214-4273-3. Detail

2010

  • LUKÁŠ Roman and MEDUNA Alexander. Multigenerative Grammar Systems and Matrix Grammars. Kybernetika, vol. 46, no. 1, 2010, pp. 68-82. ISSN 0023-5954. Detail
Back to top