How treewidth helps in verification
- 1 January 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGLOG News
- Vol. 9 (1), 6-21
- https://doi.org/10.1145/3527540.3527542
Abstract
Treewidth, or similar measures, have been a quite useful technique in the verification of infinite state systems. We illustrate, through examples, how such measures help in analyzing a system.Keywords
This publication has 23 references indexed in Scilit:
- Algorithmic meta-theoremsPublished by Cambridge University Press (CUP) ,2011
- Adding nesting structure to wordsJournal of the ACM, 2009
- The monadic second-order logic of graphs XV: On a conjecture by D. SeeseJournal of Applied Logic, 2006
- MULTI-PUSH-DOWN LANGUAGES AND GRAMMARSInternational Journal of Foundations of Computer Science, 1996
- Verifying Programs with Unreliable ChannelsInformation and Computation, 1996
- The structure of the models of decidable monadic theories of graphsAnnals of Pure and Applied Logic, 1991
- On Communicating Finite-State MachinesJournal of the ACM, 1983
- Decidability of Second-Order Theories and Automata on Infinite TreesTransactions of the American Mathematical Society, 1969
- Decision Problems of Finite Automata Design and Related ArithmeticsTransactions of the American Mathematical Society, 1961
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960