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

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

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
• scientific article; zbMATH DE number 4180775
• The expressive power of fixed-point logic with counting

Cited in

(16)

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

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)