Finite satisfiability for guarded fixpoint logic

DOI10.1016/J.IPL.2012.02.005zbMATH Open1243.68191arXiv1104.2262OpenAlexW1749183653MaRDI QIDQ436331FDOQ436331

Mikołaj Bojańczyk, Vince Bárány

Publication date: 20 July 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: The finite satisfiability problem for guarded fixpoint logic is decidable and complete for 2ExpTime (resp. ExpTime for formulas of bounded width).

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

zbMATH Keywords

formal methodsfinite satisfiabilityguarded fixpoint logicguarded fragment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Modal languages and bounded fragments of predicate logic
• Querying the Guarded Fragment
• On the Restraining Power of Guards
• Back and forth between guarded and modal logics

Cited In (5)

• Guarded negation
• Title not available (Why is that?)
• On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity
• Guarded quantification in least fixed point logic
• On the complexity of team logic and its two-variable fragment

This page was built for publication: Finite satisfiability for guarded fixpoint logic

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