From bidirectionality to alternation.

DOI10.1016/S0304-3975(02)00410-3MaRDI QIDQ1401248zbMATH OpenOpenAlexFDO

Authors 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, https://figshare.com/articles/journal_contribution/From_bidirectionality_to_alternation/10104554

zbMATH Keywords

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• From bidirectionality to alternation
• Two-way finite automata: old and recent results
• Alternation in two-way finite automata
• One alternation can be more powerful than randomization in small and fast two-way finite automata
• Constructions for alternating finite automata^∗

Cites work

• A note on the reduction of two-way automata to one-way automata
• Alternating automata on infinite trees
• Alternating finite automata on -words
• Alternating Pushdown and Stack Automata
• Alternation
• An automata-theoretic approach to reasoning about infinite-state systems
• Automatic generation of efficient lexical processors using finite state techniques
• Complexity results for two-way and multi-pebble automata and their logics
• CTL^+ is exponentially more succinct than CTL
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Endmarkers can make a difference
• scientific article; zbMATH DE number 1069482 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• scientific article; zbMATH DE number 3328721 (Why is no real title available?)
• Nondeterminism and the size of two way finite automata
• On equations for regular languages, finite automata, and sequential networks
• Properties that characterize LOGCFL
• Propositional dynamic logic of looping and converse is elementarily decidable
• Reasoning about the past with two-way automata
• State-complexity of finite-state devices, state compressibility and incompressibility
• Testing and generating infinite sequences by a finite automaton
• Theories of automata on \(\omega\)-tapes: a simplified approach
• Tree-size bounded alternation
• Weak alternating automata are not that weak

Cited in

(7)

• Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
• Alternation in two-way finite automata
• An automata-theoretic approach to infinite-state systems
• scientific article; zbMATH DE number 4027669 (Why is no real title available?)
• From bidirectionality to alternation
• Boundedness of conjunctive regular path queries
• Bidirectionalization for free! (Pearl)

This page was built for publication: From bidirectionality to alternation.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401248)