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 |

Authors (1 rows)

Cited by (10 rows)

References (16 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Martin Lange | 1 | 44 | 4.03 |