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

2 of 2

2008	Pardubska, D., Platek, M., Otto, F., 2008. On PCGS and FRR-automata, in: Vojtas, P. (Hrsg.), ITAT 2008, Proc. Department of Computer Science, Faculty of Science, Pavol Jozef Safarik University, Kosice, S. 41–47.
2008	Otto, F., Mraz, F., Jurdzinski, T., Platek, M., 2008. On the complexity of 2-monotone restarting automata. Theory of Computing Systems 42, 488–518. https://doi.org/10.1007/s00224-007-9004-y
2007	Mraz, F., Platek, M., Otto, F., 2007. A measure for the degree of nondeterminism of context-free languages, in: Holub, J. and Z. (Hrsg.), CIAA 2007, Proceedings. Springer, Berlin, S. 192–202.
2007	Mraz, F., Otto, F., Platek, M., 2007. Free word-order and restarting automata, in: Loos, R. (Hrsg.), LATA 2008, Preproceedings. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, S. 425–436. https://doi.org/10.3233/FI-2014-1083
2007	Messerschmidt, H., Otto, F., 2007. On determinism versus nondeterminism for restarting automata, in: Loos, R. (Hrsg.), LATA 2007, Preproceedings. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, S. 413–424.
2004	Jurdzinski, T., Otto, F., Mraz, F., Platek, M., 2004. On the complexity of 2-monotone restarting automata, in: Calude, C.S. (Hrsg.), Developments in Language Theory, Proceedings DLT 2004. Springer, Berlin, S. 237–248.