On linear languages recognized by deterministic biautomata

Logo poskytovatele

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Autoři

JIRÁSKOVÁ Galina KLÍMA Ondřej

Rok publikování 2022
Druh Článek v odborném periodiku
Časopis / Zdroj Information and Computation
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
www https://www.sciencedirect.com/science/article/pii/S0890540121000936#!
Doi http://dx.doi.org/10.1016/j.ic.2021.104778
Klíčová slova Linear languages; Deterministic biautomata; Deterministic linear grammars
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info