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 Lange | 1 | 44 | 4.03 |