A note on the reduction of two-way automata to one-way automata
From MaRDI portal
Publication:1116341
DOI10.1016/0020-0190(89)90205-6zbMath0665.68045OpenAlexW1977193848WikidataQ57380757 ScholiaQ57380757MaRDI QIDQ1116341
Publication date: 1989
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(89)90205-6
Related Items
State-complexity of finite-state devices, state compressibility and incompressibility, Semantic Acyclicity on Graph Databases, Complementing two-way finite automata, Regular language representations in the constructive type theory of Coq, View-based query processing: on the relationship between rewriting, answering and losslessness, State succinctness of two-way finite automata with quantum and classical states, From Two-Way to One-Way Finite Automata—Three Regular Expression-Based Methods, Converting two-way nondeterministic unary automata into simpler automata., From bidirectionality to alternation., Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic, On the transformation of two-way finite automata to unambiguous finite automata, Deciding FO-definability of regular languages, On the transformation of two-way deterministic finite automata to unambiguous finite automata, Simple picture processing based on finite automata and regular grammars, On the state complexity of operations on two-way finite automata, New size hierarchies for two way automata, On the complexity of typechecking top-down XML transformations, On regular temporal logics with past, Unnamed Item, The zig-zag power series: A two-way version of the \({}^*\) operator., A more efficient notion of zigzag stability, Origin-equivalence of two-way word transducers is in PSPACE, Two-Way Automata in Coq, Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
Cites Work
