Guarded quantification in least fixed point logic

DOI10.1023/A:1026107209351MaRDI QIDQ1424969zbMATH OpenOpenAlexFDO

Authors Gregory Loren McColm

Publication date 15 March 2004

Published in Journal of Logic, Language and Information (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1026107209351

zbMATH Keywords

game representations of logicsgame-theoretic semanticsguarded quantificationleast fixed point logicpositive elementary induction

Mathematics Subject Classification ID

Logic in computer science (03B70) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19) Games involving graphs (91A43)

Review text

The author develops a variant of least fixed point logic based on first-order logic with a relaxed version of guarded quantification. He develops a game-theoretic semantics of this logic, and finds that under reasonable conditions, guarding quantification does not reduce the expressibility of least fixed point logic. He also finds that the guarded version of a least fixed point algorithm may have a greater time complexity than the unguarded version, by a linear factor.

Recommendations

• Finite satisfiability for guarded fixpoint logic
• The complexity of boundedness for guarded logics
• Introduction to Guarded Logics
• Guards, bounds, and generalized semantics
• Automata for Guarded Fixed Point Logics
• Bisimulation quantifiers and uniform interpolation for guarded first order logic
• A note on guarded theories
• scientific article; zbMATH DE number 1341606
• scientific article; zbMATH DE number 1043779
• Fixed-point logics, generalized quantifiers, and oracles

Cited in

(3)

• scientific article; zbMATH DE number 6215728 (Why is no real title available?)
• SOME MODEL THEORY OF GUARDED NEGATION
• Bisimulation quantifiers and uniform interpolation for guarded first order logic

This page was built for publication: Guarded quantification in least fixed point logic

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