Finite satisfiability for guarded fixpoint logic

DOI10.1016/J.IPL.2012.02.005MaRDI QIDQ436331zbMATH OpenOpenAlexFDO

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

Publication date 20 July 2012

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

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)

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

Cites work

• scientific article; zbMATH DE number 1223729 (Why is no real title available?)
• scientific article; zbMATH DE number 2086675 (Why is no real title available?)
• Back and forth between guarded and modal logics
• Modal languages and bounded fragments of predicate logic
• On the Restraining Power of Guards
• Querying the Guarded Fragment

Cited in

(5)

• scientific article; zbMATH DE number 6215728 (Why is no real title available?)
• Guarded quantification in least fixed point logic
• On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity
• Guarded negation
• 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)