Two-Way Non-Uniform Finite Automata

DOI10.1142/s0129054122440063OpenAlexW4311244946MaRDI QIDQ6169962

Juraj Hromkovič, Richard Královič, Fabian Frei, Rastislav Královič

Publication date: 15 August 2023

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054122440063

zbMATH Keywords

two-way finite automataspace complexitynon-uniformity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Turing machines that take advice
• Theory of one-tape linear-time Turing machines
• Amount of nonconstructivity in deterministic finite automata
• Two-way automata versus logarithmic space
• Multitape one-way nonwriting automata
• On initial segment complexity and degrees of randomness
• Automata that take advice
• Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
• FINITE AUTOMATA WITH ADVICE TAPES
• Some Results on Tape-Bounded Turing Machines
• The definition of random sequences
• Determinism and Nondeterminism in Finite Automata with Advice

This page was built for publication: Two-Way Non-Uniform Finite Automata