Fixed-point extensions of first-order logic
From MaRDI portal
Publication:1090327
DOI10.1016/0168-0072(86)90055-2zbMath0621.03013WikidataQ105978978 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
least fixed point; expressive power on finite structures; fixed-point-extensions of first-order logic; inflationary fixed point predicate; monotone fixed point predicate
03B60: Other nonclassical logic
Related Items
On fixed-point logic with counting, Complete problems for fixed-point logics, Tailoring recursion for complexity, The expressive power of fixed-point logic with counting, On the expressive power of counting, The alternating fixpoint of logic programs with negation, Finite-model theory -- A personal perspective, 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, 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, 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, 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\), Almost Everywhere Equivalence of Logics in Finite Model Theory, Finite Variable Logics in Descriptive Complexity Theory
