Projekt 3 - Eigentliche Sprachen von Restart Automaten (On Proper Languages of Restarting Automata)

(Beginn: 01/2007)

Motivated by the way in which sentences of natural languages are analyzed in linguistics, we study automata that work on extended alphabets that in addition to the input symbols also contain certain auxiliary symbols. These auxiliary symbols model the use of (morphological, syntactical, and semantical) categories in the process of analyzing sentences. The automata we consider work on so-called characteristic languages, that is, on languages that include auxiliary symbols. The proper language is obtained from a characterisitc language by removing all occurrences of auxiliary symbols. By requiring that the automata are lexicalized, we restrict the lengths of blocks of auxiliary symbols that are admitted. We investigate classes of proper languages for various restricted types of deterministic restarting automata that are lexicalized.

Mitarbeiter:

Dr. František Mráz
Faculty of Mathematics and Physics, Department of Computer Science, Charles University, Prag

Dr. Martin Plátek
Faculty of Mathematics and Physics, Department of Computer Science, Charles University, Prag

Prof. Dana Pardubská
Department of Computer Science, Comenius University, Bratislava

Veröffentlichungen:

Plátek, M., Otto, F., Mráz, F.:
On h-lexicalized restarting list automata, Technical Report.
Mráz, F., Otto, F. and Plátek, M.:
Free word-order and restarting automata
Fundamenta Informaticae 133 (2014) 399-419.
Pardubská, D., Plátek M. and Otto, F.:
On the correspondence between parallel communicating grammar systems and restarting automata.
In Bel-Enguix, G. and Jiménez-López, M.D., editors, Bio-Inspired Models for Natural and Formal Languages, pages 153-188, Cambridge Scholar Publishing, Newcastle upon Tyne, 2011.
Pardubská, D., Plátek M. and Otto, F.:
Parallel communicating grammar systems with regular control and skeleton preserving FRR automata.
Theoretical Computer Science 412 (2011) 458-477.
Otto, F.:
On proper languages and transformations of lexicalized types of automata.
In Ito, M., Kobayashi, Y. and Shoji, K., editors, Automata, Formal Languages and Algebraic Systems, Proc. of AFLAS 2008, pages 201-222, World Scientific, Singapore, 2010.
Otto, F., Plátek M. and Mráz, F.:
On lexicalized well-behaved restarting automata that are monotone.
In Gao, Y., Lu, H., Seki, Sh. and Yu, Sh., editors, DLT 2010, Proc. Lecture Notes in Computer Science 6224, pages 352-363, Springer, Berlin, 2010.
Plátek, M., Otto, F. and Mráz, F.:
Two-dimensional hierarchies of proper languages of lexicalized FRR-automata.
Information and Computation 207 (2009) 1300-1314.
Pardubská, D., Plátek, M. and Otto, F.:
Parallel communicating grammars systems with regular control.
In Bozapalidis, S. and Rahonis, G., editors, Algebraic Informatics, CAI 2009, Proc. Lecutre Notes in Computer Science 5725, pages 342-360, Springer, Berlin, 2009.
Mráz, F., Otto, F. and Plátek, M.:
The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages.
Theoretical Computer Science 410 (2009) 3530-3538.
Otto, F.:
Left-to-right regular languages and two-way restarting automata.
RAIRO Informatique Théorique et Applications 43 (2009) 653-665.
Pardubská, D., Plátek, M. and Otto, F.:
On parallel communicating grammars systems and correctness preserving restarting automata
In Dediu, A.H., Ionescu, A.M. and Martin-Vide, C., editors, Language and Automata Theory and Applications, LATA 2009, Proc., Lecture Notes in Computer Science 5457, pages 660-671, Springer, Berlin, 2009.
Pardubská, D., Plátek, M. and Otto, F.:
On PCGS and FRR-automata
In Vojtás, P., editor, Information Technologies - Applications and Theory, ITAT 2008, Proc., pages 41-47, Department of Computer Science, Faculty of Science, Pavol Jozef Safárik University, Kosice, 2008.
Otto, F. and Plátek, M.:
A two-dimensional taxonomy of proper languages of lexicalized FRR-automata
In Martin-Vide, C., Otto, F. and Fernau, H., editors, Language and Automata Theory and Applications, LATA 2008, Proc., Lecture Notes in Computer Science 5196, pages 409-420, Springer, Berlin, 2008.
Jurdzinski, T., Otto, F., Mráz, F. and Plátek, M.:
On the complexity of 2-monotone restarting automata, Theory of Computing Systems 42 (2008) 488-518.
Mráz, F., Plátek, M. and Otto, F.:
A measure for the degree of nondeterminism of context-free languages
In Holub, J. and Zd'árek, J., editors, CIAA 2007, Proceedings, Lecture Notes in Computer Science 4783, pages 192-202, Springer, Berlin, 2007.
Messerschmidt, H. and Otto, F.:
On determinism versus nondeterminism for restarting automata
In Loos, R., Fazekas, S.Z. and Martin-Vide, C., editors, LATA 2007, Preproceedings , Report 35/07, pages 413-424, Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, 2007.
Mráz, F., Otto, F. and Plátek, M.:
Free word-order and restarting automata
In Loos, R., Fazekas, S.Z. and Martin-Vide, C., editors, LATA 2007, Preproceedings , Report 35/07, pages 425-436, Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, 2007.