Verification of Two-Variable Logic Revisited
Authors:
- Michael BenediktMBMichael Benedikt
- Rastislav LenhardtRLRastislav Lenhardt
- James WorrellJWJames Worrell
- 1 September 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 114-123
Abstract
Two-variable logic is a fragment of first-order logic that allows for decidable verification problems. In previous work, we developed an approach to FO2 verification that is particularly useful for probabilistic systems, based on analysis of the translation of FO2 to automata. In this work we show that the techniques introduced there can be applied to give information on other logics, and can be used in conjunction with automata-theoretic techniques for Linear Temporal Logic (LTL) in the context of probabilistic verification. First we revisit the technique of our prior work starting with FO2 without the successor relation. Making use of recent results by Weis we show here that we can get quite small automata for these formula. We then show that we can recapture the automata size bounds for general FO2 formulas by bootstrapping results for FO2 without successor. Next, we look at combining FO2 verification techniques with those for LTL. We present here a language that subsumes both FO2 and LTL, and inherits the model checking properties of both languages. Our automata translation gives new bounds on model-checking for this large language for non-deterministic systems, and is particularly useful for probabilistic systems: e.g Markov Chains, Recursive Markov Chains, and Markov Decision Processes.Keywords
This publication has 7 references indexed in Scilit:
- Two Variable vs. Linear Temporal Logic in Model Checking and GamesLecture Notes in Computer Science, 2011
- Analysis of recursive state machinesACM Transactions on Programming Languages and Systems, 2005
- Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations2005
- First-Order Logic with Two Variables and Unary Temporal LogicInformation and Computation, 2002
- Nonrelativizing separations2002
- The complexity of probabilistic verificationJournal of the ACM, 1995
- Temporal and Modal Logic1990