From bidirectionality to alternation.
From MaRDI portal
Publication:1401248
DOI10.1016/S0304-3975(02)00410-3zbMath1044.68101OpenAlexW1491652234MaRDI QIDQ1401248
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
Nondeterministic finite automataAlternating finite automataAlternating Büchi automataNondeterministic Büchi automataTwo-way automata
Related Items (3)
An Automata-Theoretic Approach to Infinite-State Systems ⋮ Unnamed Item ⋮ Alternation in two-way finite automata
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: From bidirectionality to alternation.
