Publication details

Deterministic Biautomata and Subclasses of Deterministic Linear Languages

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: