Informace o publikaci
Deterministic Biautomata and Subclasses of Deterministic Linear Languages
| Autoři | |
|---|---|
| Rok publikování | 2019 |
| Druh | Článek ve sborníku |
| Konference | Language and Automata Theory and Applications |
| Fakulta / Pracoviště MU | |
| 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: |