Infinitary logic and inductive definability over finite structures

DOI10.1006/INCO.1995.1084zbMath0834.68029OpenAlexW2037071126WikidataQ58215767 ScholiaQ58215767MaRDI QIDQ1893734

Anuj Dawar, Scott Weinstein, Steven Lindell

Publication date: 2 August 1995

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://repository.upenn.edu/cgi/viewcontent.cgi?article=1376&context=cis_reports

zbMATH Keywords

complexity classesmachine model of generic computation

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (27)

Finite Variable Logics in Descriptive Complexity Theory ⋮ Canonization for two variables and puzzles on the square ⋮ The first order definability of graphs: Upper bounds for quantifier depth ⋮ How to define a linear order on finite models ⋮ A query language for NC ⋮ The Kolmogorov expressive power of Boolean query languages ⋮ Preservation theorems in finite model theory ⋮ A query language for NC (extended abstract) ⋮ On complexity of Ehrenfeucht-Fraïssé games ⋮ On the Decision Problem for Two-Variable First-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 ⋮ Computing on structures ⋮ Computing with infinitary logic ⋮ The \(k\)-variable property is stronger than H-dimension \(k\) ⋮ Implicit definability and infinitary logic in finite model theory ⋮ A restricted second order logic for finite structures ⋮ On the expressibility and the computability of untyped queries ⋮ Relation algebras from cylindric algebras. I ⋮ Large finite structures with few \(L^k\)-types ⋮ Infinitary logic for computer science ⋮ A restricted second order logic for finite structures ⋮ The Relational Polynomial-Time Hierarchy and Second-Order Logic ⋮ Querying spatial databases via topological invariants ⋮ Stability theory, permutations of indiscernibles, and embedded finite models ⋮ On fixed-point logic with counting

This page was built for publication: Infinitary logic and inductive definability over finite structures