Deterministic Biautomata and Subclasses of Deterministic Linear Languages

Varování

Publikace nespadá pod Fakultu sportovních studií, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.

Autoři	JIRÁSKOVÁ Galina KLÍMA Ondřej
Rok publikování	2019
Druh	Článek ve sborníku
Konference	Language and Automata Theory and Applications
Fakulta / Pracoviště MU	Přírodovědecká fakulta
Citace
www	https://rd.springer.com/chapter/10.1007%2F978-3-030-13435-8_23
Doi	http://dx.doi.org/10.1007/978-3-030-13435-8_23
Klíčová slova	Linear Languages; Descriptional complexity;
Popis	We propose the notion of a deterministic biautomaton, a machine reading an input word from both ends. We focus on various subclasses of deterministic linear languages and give their characterizations by certain subclasses of deterministic biautomata. We use these characterizations to establish closure properties of the studied subclasses of languages and to get basic decidability results concerning them.
Související projekty:	Centrum excelence - Institut teoretické informatiky