Fixed-point extensions of first-order logic

DOI10.1016/0168-0072(86)90055-2zbMath0621.03013OpenAlexW2059144726WikidataQ105978978 ScholiaQ105978978MaRDI QIDQ1090327

Publication date: 1986

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2027.42/26387

zbMATH Keywords

least fixed point expressive power on finite structures fixed-point-extensions of first-order logic inflationary fixed point predicate monotone fixed point predicate

Mathematics Subject Classification ID

Other nonclassical logic (03B60)

Related Items

On inflationary fix-point operators safety, Finite Variable Logics in Descriptive Complexity Theory, What Is an Algorithm?, Expressive equivalence of least and inflationary fixed-point logic, The nested universal relation data model, Symbioses between mathematical logic and computer science, Generalized quantifiers and pebble games on finite structures, Semantic Restrictions over Second-Order Logic, Inductive definitions over finite structures, Database querying under changing preferences, How to define a linear order on finite models, Hierarchies in transitive closure logic, stratified Datalog and infinitary logic, Descriptive complexity of deterministic polylogarithmic time and space, Using automata theory for characterizing the semantics of terminological cycles, Metafinite model theory, Circumscribing DATALOG: expressive power and complexity, Complexity and undecidability results for logic programming, Complete problems for fixed-point logics, Bounded fixpoints for complex objects, Tailoring recursion for complexity, Logics capturing relativized complexity classes uniformly, Program completion in the input language of GRINGO, Partial fixed point for finite models in second order logic, Linear ordering on graphs, anti-founded sets and polynomial time computability, Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus, The expressive power of fixed-point logic with counting, Why not negation by fixpoint?, Computing on structures, An analysis of fixed-point queries on binary trees, On the expressive power of counting, The descriptive complexity of decision problems through logics with relational fixed-point and capturing results, Capturing complexity classes by fragments of second-order logic, Infinitary logics and 0-1 laws, A restricted second order logic for finite structures, Metafinite model theory, Inferring null join dependencies in relational databases, The alternating fixpoint of logic programs with negation, Finite-model theory -- A personal perspective, Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs, Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs, Semantics and expressive power of nondeterministic constructs in deductive databases, A restricted second order logic for finite structures, Inductive situation calculus, 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\), Logic and Game Theory, Almost Everywhere Equivalence of Logics in Finite Model Theory, An algebra for pomsets., Equivalence and normal forms for the restricted and bounded fixpoint in the nested algebra, Hereditarily-finite sets, data bases and polynomial-time computability, The expressive power of stratified logic programs, On fixed-point logic with counting, Context-sensitive transitive closure operators, Canonisation and Definability for Graphs of Bounded Rank Width, Querying datalog programs with temporal logic

Cites Work