Computing the Rabin Index of a Parity Automaton

DOI10.1051/ita:1999129zbMath0958.68089OpenAlexW1989863177MaRDI QIDQ4953338

Ramón MacEiras, Olivier Carton

Publication date: 9 April 2001

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_1999__33_6_495_0/

zbMATH Keywords

Rabin indexparity automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (7)

On Minimization and Learning of Deterministic ω-Automata in the Presence of Don’t Care Words ⋮ The Rabin index of parity games: its complexity and approximation ⋮ A gap property of deterministic tree languages. ⋮ Unnamed Item ⋮ New Optimizations and Heuristics for Determinization of Büchi Automata ⋮ Deciding low levels of tree-automata hierarchy ⋮ Automata on infinite trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the rabin index of a regular language of infinite words
• Hierarchies of weak automata and weak monadic formulas
• Chain automata
• On ω-regular sets
• Structural complexity of ω-automata
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Computing the Rabin Index of a Parity Automaton