A Step Up in Expressiveness of Decidable Fixpoint Logics

DOI10.1145/2933575.2933592MaRDI QIDQ4635946zbMATH OpenOpenAlexWikidataFDO

Authors Michael Benedikt, Pierre Bourhis, Michael Vanden Boom

Publication date 23 April 2018

Published in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01413890/file/LICS16-gnfpup-long.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70)

Recommendations

• Characterizing definability in decidable fixpoint logics
• Axiomatizing fixpoint logics
• scientific article; zbMATH DE number 1043779
• A Decidable Non-Regular Modal Fixpoint Logic
• scientific article; zbMATH DE number 7104937
• A fixpoint semantics for disjunctive logic programs
• Fixed-point extensions of first-order logic
• Approximation fixpoint theory and the well-founded semantics of higher-order logic programs
• Publication:3204028
• The expressive power of fixed-point logic with counting

Cited in

(13)

• Guarded fixed point logics and the monadic theory of countable trees.
• Guarded negation
• The descriptive complexity of decision problems through logics with relational fixed-point and capturing results
• Means and limits of decision (invited talk)
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• scientific article; zbMATH DE number 7104937 (Why is no real title available?)
• scientific article; zbMATH DE number 7561597 (Why is no real title available?)
• Guarded Ontology-Mediated Queries
• Space-efficient fragments of higher-order fixpoint logic
• Guarded negation
• Evaluating Datalog via tree automata and cycluits
• Characterizing definability in decidable fixpoint logics
• An improved algorithm for the evaluation of fixpoint expressions

This page was built for publication: A Step Up in Expressiveness of Decidable Fixpoint Logics

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