From bidirectionality to alternation.

DOI10.1016/S0304-3975(02)00410-3zbMath1044.68101OpenAlexW1491652234MaRDI QIDQ1401248

Nir Piterman, Moshe Y. Vardi

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00410-3

zbMATH Keywords

Nondeterministic finite automataAlternating finite automataAlternating Büchi automataNondeterministic Büchi automataTwo-way automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

An Automata-Theoretic Approach to Infinite-State Systems ⋮ Unnamed Item ⋮ Alternation in two-way finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On equations for regular languages, finite automata, and sequential networks
• Alternating finite automata on \(\omega\)-words
• Endmarkers can make a difference
• Alternating automata on infinite trees
• A note on the reduction of two-way automata to one-way automata
• Tree-size bounded alternation
• Properties that characterize LOGCFL
• Theories of automata on \(\omega\)-tapes: a simplified approach
• Complexity results for two-way and multi-pebble automata and their logics
• Alternating Pushdown and Stack Automata
• Weak alternating automata are not that weak
• Propositional dynamic logic of looping and converse is elementarily decidable
• Alternation
• State-complexity of finite-state devices, state compressibility and incompressibility
• Nondeterminism and the size of two way finite automata
• Automatic generation of efficient lexical processors using finite state techniques
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees