Complement for two-way alternating automata

DOI10.1007/s00236-020-00373-8OpenAlexW4250053099MaRDI QIDQ5919102

Mohammad Zakzok, Viliam Geffert, Christos A. Kapoutsis

Publication date: 30 September 2021

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-020-00373-8

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Descriptive complexity and finite models (68Q19) Theory of computing (68Qxx)

Related Items

Improved complement for two-way alternating automata ⋮ State complexity of union and intersection on graph-walking automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An alternating hierarchy for finite automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• A speed-up theorem without tape compression
• Some observations concerning alternating Turing machines using small space
• The method of forced enumeration for nondeterministic automata
• Halting space-bounded computations
• Turing machines with sublogarithmic space
• Complementing two-way finite automata
• Reversibility of Computations in Graph-Walking Automata
• Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
• Alternating Pushdown and Stack Automata
• Size Complexity of Two-Way Finite Automata
• Nondeterministic Space is Closed under Complementation
• Alternation
• Nondeterminism and the size of two way finite automata
• Complement for two-way alternating automata