Accepting runs in a two-way finite automaton

DOI10.1016/J.IC.2018.03.002MaRDI QIDQ1753992zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, Zhe Dang, Qin Li

Publication date 30 May 2018

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

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

zbMATH Keywords

samplingtwo-way automataaccepting run

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Sampling a two-way finite automaton
• Two-way finite automata: old and recent results
• Alternation in two-way finite automata
• scientific article; zbMATH DE number 1318511
• On the length of shortest strings accepted by two-way finite automata

Cites work

• Automata with Reversal-Bounded Counters: A Survey
• Deterministic context free languages
• Execution information rate for some classes of automata
• New Decidability Results Concerning Two-Way Counter Machines
• One-way stack automata
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Reversal-bounded multipushdown machines
• Sampling automata and programs
• Some decision problems concerning semilinearity and commutation.
• The complexity of decision problems for finite-turn multicounter machines

Cited in

(2)

• Decision problems and projection languages for restricted variants of two-dimensional automata
• Sampling a two-way finite automaton

This page was built for publication: Accepting runs in a two-way finite automaton

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1753992)