Paper Info
Title
Weak automata for the linear time µ-calculus
Abstract
This paper presents translations forth and back between formulas of the linear time μ-calculus and finite automata with a weak parity acceptance condition. This yields a normal form for these formulas, in fact showing that the linear time alternation hierarchy collapses at level 0 and not just at level 1 as known so far. The translation from formulas to automata can be optimised yielding automata whose size is only exponential in the alternation depth of the formula.
Year
DOI
Venue
2005
10.1007/978-3-540-30579-8_18
VMCAI
Keywords
Field
DocType
weak parity acceptance condition,finite automaton,alternation depth,normal form,linear time,weak automaton,linear time alternation hierarchy,finite automata
Quantum finite automata,Exponential function,Abstract interpretation,Computer science,Automaton,Pure mathematics,Algorithm,Theoretical computer science,Finite-state machine,Time complexity,ω-automaton,Alternation (linguistics)
Conference
ISBN
Citations 
PageRank 
3-540-24297-X
10
0.56
References 
Authors
16
1
Name
Order
Citations
PageRank
Martin Lange1444.03