Eigentliche Sprachen von Restart Automaten - Research Information System | University of Kassel

without external funding

Eigentliche Sprachen von Restart Automaten

Project Details

Project duration: 01/2007–12/2012

Website: http://www.theory.informatik.uni-kassel.de/projekte

Abstract

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.

Publications

1 of 2

2011	Pardubska, D., Platek, M., Otto, F., 2011. On the correspondence between parallel communicating grammar systems and restarting automata, in: Bel-Enguix, G. and J.-L. (Hrsg.), Bio-Inspired Models for Natural and Formal Languages. Cambridge Scholar Publishing, Newcastle upon Tyne, S. 153–188.
2011	Pardubska, D., Platek, M., Otto, F., 2011. Parallel communicating grammar systems with regular control and skeleton preserving FRR automata. Theoretical Computer Science 412, 458–477. https://doi.org/10.1016/j.tcs.2010.10.017
2010	Otto, F., Platek, M., Mraz, F., 2010. On lexicalized well-behaved restarting automata that are monotone, in: Gao, Y. (Hrsg.), 14th International Conference, DLT 2010, London, ON, Canada, August 17-20, 2010. Proceedings. Springer, Berlin, S. 352–363. https://doi.org/10.1007/978-3-642-14455-4_32
2010	Otto, F., 2010. On proper languages and transformations of lexicalized types of automata, in: Ito, M., Kobayashi, Y., Shoji, K. (Hrsg.), Automata, Formal Languages and Algebraic Systems, Proc. of AFLAS 2008. World Scientific, Singapore, S. 201–222.
2009	Otto, F., 2009. Left-to-right regular languages and two-way restarting automata. RAIRO: Theoretical Informatics and Applications 43, 653–665. https://doi.org/10.1051/ita/2009013
2009	Pardubska, D., Platek, M., Otto, F., 2009. On parallel communicating grammars systems and correctness preserving restarting automata, in: Dediu, A.H., Ionescu, A.M., Martin-Vide, C. (Hrsg.), Language and automata theory and applications. Springer, Berlin, S. 660–671. https://doi.org/10.1007/978-3-642-00982-2_56
2009	Pardubska, D., Platek, M., Otto, F., 2009. Parallel communicating grammars systems with regular control, in: Bozapalidis, S. and R. (Hrsg.), Algebraic Informatics, CAI 2009, Proc. Springer, Berlin, S. 342–360. https://doi.org/10.1007/978-3-642-03564-7_23
2009	Mraz, F., Otto, F., Platek, M., 2009. The degree of word-expansion of lexicalized RRWW-automata - A new measure for the degree of nondeterminism of (context-free) languages. Teoretical Computer Science 410, 3530–3538. https://doi.org/10.1016/j.tcs.2009.03.017
2009	Platek, M., Otto, F., Mraz, F., 2009. Two-dimensional hierarchies of proper languages of lexicalized FRR-automata. Information and Computation 207, 1300–1314. https://doi.org/10.1016/j.ic.2009.02.011
2008	Otto, F., Platek, M., 2008. A two-dimensional taxonomy of proper languages of lexicalized FRR-automata, in: Martin-Vide, C. (Hrsg.), LATA 2008, Proceedings. Springer, Berlin, S. 409–420.