Deterministic Biautomata and Subclasses of Deterministic Linear Languages

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. 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:

You are running an old browser version. We recommend updating your browser to its latest version.