Deterministic Biautomata and Subclasses of Deterministic Linear Languages

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Science. Official publication website can be found on muni.cz.

Authors	JIRÁSKOVÁ Galina KLÍMA Ondřej
Year of publication	2019
Type	Article in Proceedings
Conference	Language and Automata Theory and Applications
MU Faculty or unit	Faculty of Science
Citation
web	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
Keywords	Linear Languages; Descriptional complexity;
Description	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.
Related projects:	Centrum excelence - Institut teoretické informatiky