From bidirectionality to alternation.
From MaRDI portal
Publication:1401248
DOI10.1016/S0304-3975(02)00410-3zbMath1044.68101MaRDI QIDQ1401248
Publication date: 17 August 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Nondeterministic finite automata; Alternating finite automata; Alternating Büchi automata; Nondeterministic Büchi automata; Two-way automata
68Q45: Formal languages and automata
Related Items
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
