Deterministic Biautomata and Subclasses of Deterministic Linear Languages
| Authors | |
|---|---|
| Year of publication | 2019 |
| Type | Article in Proceedings |
| Conference | Language and Automata Theory and Applications |
| MU Faculty or unit | |
| 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: |