Unambiguous Büchi automata.

DOI10.1016/S0304-3975(02)00618-7zbMath1044.68084OpenAlexW2111715088MaRDI QIDQ1401292

Olivier Carton, Max Michel

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)00618-7

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words ⋮ From LTL to unambiguous Büchi automata via disambiguation of alternating automata ⋮ Green's relations in finite transformation semigroups ⋮ On the power of finite ambiguity in Büchi complementation ⋮ Schützenberger and Eilenberg theorems for words on linear orderings ⋮ Representing regular languages of infinite words using mod 2 multiplicity automata ⋮ Forbidden Patterns for FO² Alternation Over Finite and Infinite Words ⋮ Efficient inclusion testing for simple classes of unambiguous \(\omega \)-automata ⋮ Unnamed Item ⋮ MSO Logic for Unambiguous Shared-Memory Systems ⋮ Normality and automata ⋮ Shared-Memory Systems and Charts ⋮ UNAMBIGUOUS SHARED-MEMORY SYSTEMS ⋮ Unnamed Item ⋮ From LTL to Symbolically Represented Deterministic Automata ⋮ COMPLEMENTATION OF RATIONAL SETS ON COUNTABLE SCATTERED LINEAR ORDERINGS ⋮ Green's relations in deterministic finite automata ⋮ Regular transducer expressions for regular transformations ⋮ Valuations of Weighted Automata: Doing It in a Rational Way ⋮ LTL Model Checking of Time-Inhomogeneous Markov Chains ⋮ \( \omega \)-automata ⋮ Unambiguity in Automata Theory ⋮ FACTORIZATIONS AND UNIVERSAL AUTOMATON OF OMEGA LANGUAGES ⋮ Backward Deterministic Büchi Automata on Infinite Words ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

Cites Work

• Iteration of expansions. Unambiguous semigroups
• Rational \(\omega\)-languages are non-ambiguous
• Codeterministic automata on infinite words
• Determinacy of sinking automata on infinite trees and inequalities between various Rabin's pair indices
• The complementation problem for Büchi automata with applications to temporal logic
• On the complexity of finite semigroups
• Decision problems forω-automata
• 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
• Unnamed Item