Accepting runs in a two-way finite automaton

DOI10.1016/J.IC.2018.03.002zbMATH Open1390.68397OpenAlexW2793778887MaRDI QIDQ1753992FDOQ1753992

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

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

zbMATH Keywords

samplingtwo-way automataaccepting run

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Reversal-bounded multipushdown machines
• Some decision problems concerning semilinearity and commutation.
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Automata with Reversal-Bounded Counters: A Survey
• Deterministic context free languages
• 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
• Execution information rate for some classes of automata
• New Decidability Results Concerning Two-Way Counter Machines
• Sampling automata and programs
• One-way stack automata

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)