On linear languages recognized by deterministic biautomata

Investor logo

Warning

This publication doesn't include Faculty of Medicine. 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 2022
Type Article in Periodical
Magazine / Source Information and Computation
MU Faculty or unit

Faculty of Science

Citation
Web https://www.sciencedirect.com/science/article/pii/S0890540121000936#!
Doi http://dx.doi.org/10.1016/j.ic.2021.104778
Keywords Linear languages; Deterministic biautomata; Deterministic linear grammars
Description We introduce the notion of a deterministic biautomaton, a device that reads inputs from both ends, and admits at most one computation on every input word. We show that deterministic biautomata recognize a class of languages which is properly included in the class of linear languages, and which is incomparable to the class of languages recognized by deterministic one-turn pushdown automata. We propose three restrictions of the basic model of deterministic biautomata to characterize the classes of languages generated by DL, linear LL(1), and NH-DL grammars. This results in a chain of four subclasses of linear languages in which all inclusions are strict. For these subclasses and basic operations, we show whether or not a particular class is closed under a considered operation. We prove that it is undecidable whether a linear language belongs to any of these four classes and answer some other decidability questions.
Related projects:

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

More info