On linear languages recognized by deterministic biautomata

DOI10.1016/j.ic.2021.104778zbMath1487.68148OpenAlexW3178428074MaRDI QIDQ2672654

Ondřej Klíma, Galina Jirásková

Publication date: 13 June 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2021.104778

zbMATH Keywords

linear languagesdeterministic biautomatadeterministic linear grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

Special issue: Selected papers of the 13th international conference on language and automata theory and applications, LATA 2019, On the transformation of LL\((k)\)-linear to LL(1)-linear grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• Some subclasses of context-free languages in \(NC^ 1\)
• The equivalence problem for LL- and LR-regular grammars
• Reversal-bounded multipushdown machines
• Space-bounded reducibility among combinatorial problems
• Deterministic biautomata and subclasses of deterministic linear languages
• Minimization and Characterizations for Biautomata
• Biautomata for k-Piecewise Testable Languages
• Linear Context Free Languages
• On biautomata
• NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY
• On top-to-bottom recognition and left recursion
• A machine realization of the linear context-free languages
• Mappings induced by PGSM-mappings and some recursively unsolvable problems of finite probabilistic automata