Fixed-point extensions of first-order logic
From MaRDI portal
The authors define fixed-point-extensions of first-order logic by the least fixed point predicate LFP, by the monotone fixed point predicate LFP', and the inflationary fixed point predicate IFP, respectively. It is proved that these three extensions have the same expressive power on finite structures.
Recommendations
- scientific article; zbMATH DE number 824731
- scientific article; zbMATH DE number 4180775
- Fixed Point Logics
- Extended First-Order Logic
- Fixed-point logics and computation
- scientific article; zbMATH DE number 3903941
- Publication:3204446
- Extended Lambek calculi and first-order linear logic
- Axiomatizing fixpoint logics
- Fixed-point logics, generalized quantifiers, and oracles
Cites work
- A zero-one law for logic with a fixed-point operator
- Elementary induction on abstract structures
- scientific article; zbMATH DE number 3890770 (Why is no real title available?)
- scientific article; zbMATH DE number 4008383 (Why is no real title available?)
- scientific article; zbMATH DE number 3731388 (Why is no real title available?)
- scientific article; zbMATH DE number 3602653 (Why is no real title available?)
- scientific article; zbMATH DE number 3349291 (Why is no real title available?)
- scientific article; zbMATH DE number 3378527 (Why is no real title available?)
- scientific article; zbMATH DE number 3397511 (Why is no real title available?)
- scientific article; zbMATH DE number 3188506 (Why is no real title available?)
- Model theory
- Monotone versus positive
- On monotone vs. nonmonotone induction
- On nonmonotone inductive definability
- Properties preserved in subdirect products
- The complexity of explicit definitions
Cited in
(92)- Inductive situation calculus
- Circumscribing DATALOG: expressive power and complexity
- Why not negation by fixpoint?
- An analysis of fixed-point queries on binary trees
- Capturing complexity classes by fragments of second-order logic
- Infinitary logics and 0-1 laws
- Inferring null join dependencies in relational databases
- A restricted second order logic for finite structures
- Idealization in applied first-order logic
- Hereditarily-finite sets, data bases and polynomial-time computability
- Context-sensitive transitive closure operators
- Querying datalog programs with temporal logic
- The nested universal relation data model
- How to define a linear order on finite models
- Using automata theory for characterizing the semantics of terminological cycles
- Metafinite model theory
- Bounded fixpoints for complex objects
- An expansion of basic logic with fixed points
- The descriptive complexity of decision problems through logics with relational fixed-point and capturing results
- An algebra for pomsets.
- Equivalence and normal forms for the restricted and bounded fixpoint in the nested algebra
- Expressive equivalence of least and inflationary fixed-point logic
- Generalized quantifiers and pebble games on finite structures
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- Complexity and undecidability results for logic programming
- Linear ordering on graphs, anti-founded sets and polynomial time computability
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- Partial fixed point for finite models in second order logic
- Database querying under changing preferences
- Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
- Arity hierarchies
- In the random graph \(G(n,p), p=n^{-a}\): If \(\psi\) has probability \(O(n^{-\varepsilon})\) for every \(\varepsilon >0\) then it has probability \(O(e^{-n^ \varepsilon})\) for some \(\varepsilon >0\)
- Symbioses between mathematical logic and computer science
- Inductive definitions over finite structures
- On inflationary fix-point operators safety
- Descriptive complexity of deterministic polylogarithmic time and space
- What is an algorithm?
- scientific article; zbMATH DE number 6680142 (Why is no real title available?)
- Continuous first order logic and local stability
- A logic of fixpoint definitions
- Almost Everywhere Equivalence of Logics in Finite Model Theory
- scientific article; zbMATH DE number 4180775 (Why is no real title available?)
- A Fixpoint Semantics for Ordered Logic
- Semantic restrictions over second-order logic
- \(FO(FD)\): extending classical logic with rule-based fixpoint definitions
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- One Useful Logic That Defines Its Own Truth
- scientific article; zbMATH DE number 3903941 (Why is no real title available?)
- Finite Variable Logics in Descriptive Complexity Theory
- scientific article; zbMATH DE number 1354137 (Why is no real title available?)
- Existential least fixed-point logic and its relatives
- Enhancing fixed point logic with cardinality quantifiers
- Fixed-point Logics with Nondeterministic Choice
- On fixed-point logic with counting
- Fixed Point Logics
- scientific article; zbMATH DE number 1795986 (Why is no real title available?)
- Program completion in the input language of GRINGO
- Computing on structures
- A Step Up in Expressiveness of Decidable Fixpoint Logics
- scientific article; zbMATH DE number 1841826 (Why is no real title available?)
- Complete problems for fixed-point logics
- scientific article; zbMATH DE number 824731 (Why is no real title available?)
- Tailoring recursion for complexity
- The expressive power of fixed-point logic with counting
- Some Turing-complete extensions of first-order logic
- scientific article; zbMATH DE number 7267155 (Why is no real title available?)
- An expansion of first-order Belnap-Dunn logic
- Recursive definitions and fixed-points
- Logic and Game Theory
- Inflationary fixed points in modal logic
- Automata, Languages and Programming
- Fixed-point logics and computation
- Minimal predicates, fixed-points, and definability
- Canonisation and Definability for Graphs of Bounded Rank Width
- Semantics and expressive power of nondeterministic constructs in deductive databases
- Metafinite model theory
- A restricted second order logic for finite structures
- Logics capturing relativized complexity classes uniformly
- An extension of first order limit language
- Fidel Semantics for Propositional and First-Order Version of the Logic of CG’3
- Feferman-vaught decompositions for prefix classes of first order logic
- Recursive definitions and fixed-points on well-founded structures
- Graph games and logic design
- Compositionality in context
- On undecidability of unary nonnested PFP operators for one successor function theory
- On the expressive power of counting
- The alternating fixpoint of logic programs with negation
- Finite-model theory -- A personal perspective
- NP-completeness by first-order and quantifier-free interpretations and related topics
- Logical characterizations of weighted complexity classes
- Descriptive complexity and weighted Turing machines
- The expressive power of stratified logic programs
This page was built for publication: Fixed-point extensions of first-order logic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1090327)
