Accepting runs in a two-way finite automaton

DOI10.1016/j.ic.2018.03.002zbMath1390.68397OpenAlexW2793778887MaRDI QIDQ1753992

Zhe Dang, Oscar H. Ibarra, 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)

Related Items

Decision problems and projection languages for restricted variants of two-dimensional automata

Cites Work

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