Büchi Complementation and Size-Change Termination

DOI10.1007/978-3-642-00768-2_2MaRDI QIDQ3617751zbMATH OpenOpenAlexFDO

Authors Seth Fogarty, Moshe Y. Vardi

Publication date 31 March 2009

Published in Tools and Algorithms for the Construction and Analysis of Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.6183

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Abstract: We compare tools for complementing nondeterministic B"uchi automata with a recent termination-analysis algorithm. Complementation of B"uchi automata is a key step in program verification. Early constructions using a Ramsey-based argument have been supplanted by rank-based constructions with exponentially better bounds. In 2001 Lee et al. presented the size-change termination (SCT) problem, along with both a reduction to B"uchi automata and a Ramsey-based algorithm. The Ramsey-based algorithm was presented as a more practical alternative to the automata-theoretic approach, but strongly resembles the initial complementation constructions for B"uchi automata. We prove that the SCT algorithm is a specialized realization of the Ramsey-based complementation construction. To do so, we extend the Ramsey-based complementation construction to provide a containment-testing algorithm. Surprisingly, empirical analysis suggests that despite the massive gap in worst-case complexity, Ramsey-based approaches are superior over the domain of SCT problems. Upon further analysis we discover an interesting property of the problem space that both explains this result and provides a chance to improve rank-based tools. With these improvements, we show that theoretical gains in efficiency of the rank-based approach are mirrored in empirical performance.

Recommendations

• Büchi complementation and size-change termination
• Efficient Büchi universality checking
• State of Büchi complementation
• State of Büchi complementation
• Büchi complementation made tight

Cites work

• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• Automata-Theoretic Model Checking Revisited
• Deciding full branching time logic
• Experimental Evaluation of Classical Automata Constructions
• Improved Algorithms for the Automata-Based Approach to Model-Checking
• Programming Languages and Systems
• The complementation problem for Büchi automata with applications to temporal logic
• The size-change principle for program termination
• Theories of automata on \(\omega\)-tapes: a simplified approach
• Weak alternating automata are not that weak

Cited in

(15)

• Size-change termination and satisfiability for linear-time temporal logics
• Efficient reduction of nondeterministic automata with application to language inclusion testing
• Mechanical certification of \(\mathrm{FOL_{ID}}\) cyclic proofs
• State of Büchi complementation
• Random models for evaluating efficient Büchi universality checking
• Complementing Büchi Automata with Ranker
• Advanced Ramsey-based Büchi automata inclusion testing
• Linear temporal logic symbolic model checking
• Büchi complementation and size-change termination
• Efficient Büchi universality checking
• Fixed point guided abstraction refinement for alternating automata
• Coinductive algorithms for Büchi automata
• Ramsey-based inclusion checking for visibly pushdown automata
• Sky is not the limit. Tighter rank bounds for elevator automata in Büchi automata complementation
• Simulations in rank-based Büchi automata complementation

This page was built for publication: Büchi Complementation and Size-Change Termination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3617751)