From LTL to unambiguous Büchi automata via disambiguation of alternating automata
Open Access
- 1 October 2021
- journal article
- research article
- Published by Springer Nature in Formal Methods in System Design
- Vol. 58 (1-2) , 42-82
Abstract
Due to the high complexity of translating linear temporal logic (LTL) to deterministic automata, several forms of “restricted” nondeterminism have been considered with the aim of maintaining some of the benefits of deterministic automata, while at the same time allowing more efficient translations from LTL. One of them is the notion of unambiguity. This paper proposes a new algorithm for the generation of unambiguous Büchi automata (UBA) from LTL formulas. Unlike other approaches it is based on a known translation from very weak alternating automata (VWAA) to NBA. A notion of unambiguity for alternating automata is introduced and it is shown that the VWAA-to-NBA translation preserves unambiguity. Checking unambiguity of VWAA is determined to be PSPACE-complete, both for the explicit and symbolic encodings of alternating automata. The core of the LTL-to-UBA translation is an iterative disambiguation procedure for VWAA. Several heuristics are introduced for different stages of the procedure. We report on an implementation of our approach in the tool and compare it to an existing LTL-to-UBA implementation in the tool set. Our experiments cover model checking of Markov chains, which is an important application of UBA.Keywords
Funding Information
- Deutsche Forschungsgemeinschaft (CRC 912, 389792660 as part of TRR 248)
- Deutsche Forschungsgemeinschaft (BA-1679/12-1, EXC 2050/1 (CeTI, project ID 390696704))
- Deutsche Forschungsgemeinschaft (Research Training Group QuantLA (GRK 1763))
This publication has 40 references indexed in Scilit:
- Efficient inclusion testing for simple classes of unambiguous ω-automataInformation Processing Letters, 2012
- The Complexity of Generalized Satisfiability for Linear Temporal LogicLogical Methods in Computer Science, 2009
- From linear time to branching timeACM Transactions on Computational Logic, 2005
- Unambiguous Büchi automataTheoretical Computer Science, 2003
- Efficient minimization of deterministic weak -automataInformation Processing Letters, 2001
- The logic of “initially” and “next”: Complete axiomatization and complexityInformation Processing Letters, 1999
- Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and SafraTheoretical Computer Science, 1995
- Alternating automata on infinite treesTheoretical Computer Science, 1987
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite AutomataSIAM Journal on Computing, 1985
- The complexity of propositional linear temporal logicsJournal of the ACM, 1985