Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-19T10:46:33.776Z Has data issue: false hasContentIssue false
  • English
  • Français

Three notes on the complexity of model checking fixpoint logic with chop

Published online by Cambridge University Press:  18 July 2007

Martin Lange
Martin Lange*
Affiliation:
Department of Computer Science, University of Munich, Oettingenstr. 67, 80538 München, Germany; [email protected]
Get access

Abstract

This paper analyses the complexity of model checking fixpoint logic with Chop – an extension of the modal μ-calculus with a sequential composition operator. It uses two known game-based characterisations to derive the following results: the combined model checking complexity as well as the data complexity of FLC are EXPTIME-complete. This is already the case for its alternation-free fragment. The expression complexity of FLC is trivially P-hard and limited from above by the complexity of solving a parity game, i.e. in UP ∩ co-UP. For any fragment of fixed alternation depth, in particular alternation- free formulas it is P-complete.

Keywords

Model checkinggamesEXPTIME-complete
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 41 , Issue 2 , April 2007 , pp. 177 - 190
Copyright
© EDP Sciences, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

H. Békic, Programming Languages and Their Definition, Selected Papers. Lect. Notes Comput. Sci. 177 (1984).
Browne, A., Clarke, E.M., Jha, S., Long, D.E. and Marrero, W., An improved algorithm for the evaluation of fixpoint expressions. TCS 178 (1997) 237–255. CrossRef
Cleaveland, R., Tableau-based model checking in the propositional µ-calculus. Acta Informatica 27 (1990) 725–748. CrossRef
A. Dawar, E. Grädel and S. Kreutzer, Inflationary fixed points in modal logic, in Proc. 15th Workshop on Computer Science Logic, CSL'01, edited by L. Fribourg, Paris, France. Lect. Notes Comput. Sci. 277–291 (2001).
S. Dziembowski, M. Jurdziński and D. Niwiński, On the expression complexity of the modal µ-calculus model checking. Unpublished manuscript (1996).
E.A. Emerson and C.S. Jutla, Tree automata, µ-calculus and determinacy, in Proc. 32nd Symp. on Foundations of Computer Science, San Juan, Puerto Rico 368–377 (1991). IEEE.
Emerson, E.A., Jutla, C.S. and Sistla, A.P., On model-checking for fragments of µ-calculus, in Proc. 5th Conf. on Computer Aided Verification, CAV'93. Lect. Notes Comput. Sci. 697 (1993) 385–396. CrossRef
E. Grädel, W. Thomas and Th. Wilke, Eds. Automata, Logics, and Infinite Games. Lect. Notes Comput. Sci. (2002).
Janin, D. and Walukiewicz, I., On the expressive completeness of the propositional µ-calculus with respect to monadic second order logic, in Proc. 7th Conf. on Concurrency Theory, CONCUR'96, edited by U. Montanari and V. Sassone, Pisa, Italy. Lect. Notes Comput. Sci. 1119 (1996) 263–277. CrossRef
Jurdziński, M., Deciding the winner in parity games is in UP∩co-UP. Inform. Process. Lett. 68 (1998) 119–124. CrossRef
Jurdziński, M., Small progress measures for solving parity games, in Proc. 17th Ann. Symp. on Theoretical Aspects of Computer Science, STACS'00, edited by H. Reichel and S. Tison. Lect. Notes Comput. Sci. 1770 (2000) 290–301. CrossRef
Kozen, D., Results on the propositional µ-calculus. TCS 27 (1983) 333–354. CrossRef
M. Lange, Alternating context-free languages and linear time µ-calculus with sequential composition, in Proc. 9th Workshop on Expressiveness in Concurrency, EXPRESS'02, edited by P. Panangaden and U. Nestmann, Brno, Czech Republic, Elsevier. ENTCS 68.2 (2002) 71–87.
Lange, M., Local model checking games for fixed point logic with chop, in Proc. 13th Conf. on Concurrency Theory, CONCUR'02, edited by L. Brim, P. Jančar, M. Křetínský and A. Kučera, Brno, Czech Republic. Lect. Notes Comput. Sci. 2421 (2002) 240–254. CrossRef
Lange, M. and Somla, R., The complexity of model checking higher order fixpoint logic, in Proc. 30th Int. Symp. on Math. Foundations of Computer Science, MFCS'05, edited by J. Jedrzejowicz and A. Szepietowski, Gdansk, Poland. Lect. Notes Comput. Sci. 3618 (2005) 640–651. CrossRef
Lange, M. and Stirling, C., Model checking fixed point logic with chop, in Proc. 5th Conf. on Foundations of Software Science and Computation Structures, FOSSACS'02, edited by M. Nielsen and U. H. Engberg, Grenoble, France. Lect. Notes Comput. Sci. 2303 (2002) 250–263. CrossRef
Müller-Olm, M., A modal fixpoint logic with chop, in Proc. 16th Symp. on Theoretical Aspects of Computer Science, STACS'99, edited by C. Meinel and S. Tison, Trier, Germany. Lect. Notes Comput. Sci. 1563 (1999) 510–520. CrossRef
Seidl, H., Fast and simple nested fixpoint. Inform. Process. Lett. 59 (1996) 303–308. CrossRef
Stirling, C., Local model checking games, in Proc. 6th Conf. on Concurrency Theory, CONCUR'95, edited by I. Lee and S. A. Smolka, Berlin, Germany. Lect. Notes Comput. Sci. 962 (1995) 1–11. CrossRef
Viswanathan, M. and Viswanathan, R., A higher order modal fixed point logic, in Proc. 15th Int. Conf. on Concurrency Theory, CONCUR'04, edited by Ph. Gardner and N. Yoshida, London, UK. Lect. Notes Comput. Sci. 3170 (2004) 512–528. CrossRef
Walukiewicz, I., Pushdown processes: Games and model-checking. Inform. Comput. 164 (2001) 234–263. CrossRef