The expressive power of fixed-point logic with counting
DOI10.2307/2275602zbMATH Open0854.03024OpenAlexW2097212968MaRDI QIDQ4879905FDOQ4879905
Authors: Martin Otto 
Publication date: 13 January 1997
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2275602
Recommendations
finite model theorydescriptive complexityinfinitary logicsfixed-point logicsEhrenfeucht-Fraïssé gamesLindström quantifiercardinalities of definable relationscounting pebble gamesrelational model of computation
Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other infinitary logic (03C75) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Fixed-point extensions of first-order logic
- Datalog extensions for database queries and updates
- An optimal lower bound on the number of variables for graph identification
- Relational queries computable in polynomial time
- Upper and lower bounds for first order expressibility
- Infinitary logic and inductive definability over finite structures
- Infinitary logics and 0-1 laws
Cited In (50)
- Metafinite model theory
- Capturing the polynomial hierarchy by second-order revised Krom logic
- Implicit definability and infinitary logic in finite model theory (extended abstract)
- Rank logic is dead, long live rank logic!
- Counting on CTL\(^*\): On the expressive power of monadic path logic
- Adding for-loops to first-order logic
- Fixed-point logics and computation
- Cardinality logics. I: Inclusions between languages based on ``exactly
- Canonization for two variables and puzzles on the square
- The logic of counting query answers
- Enhancing fixed point logic with cardinality quantifiers
- Combinatorial expressions and lower bounds
- A zero-one law for logic with a fixed-point operator
- Maximum matching and linear programming in fixed-point logic with counting
- Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets
- Logics with aggregate operators
- The Power of Counting Logics on Restricted Classes of Finite Structures
- Logics with counting and local properties
- Large finite structures with few \(L^k\)-types
- Pebble games for logics with counting and rank
- Henkin quantifiers: logic, games, and computation.
- First-order logic with counting: at least, \textit{weak} Hanf normal forms always exist and can be computed!
- Computing with first-order logic
- Generalising automaticity to modal properties of finite structures
- Title not available (Why is that?)
- On fixed-point logic with counting
- Dimension Versus Number of Variables, and Connectivity, too
- Counting Proportions of Sets: Expressive Power with Almost Order
- Tameness in least fixed-point logic and McColm's conjecture
- On the Descriptive Complexity of Linear Algebra
- Gaifman normal forms for counting extensions of first-order logic
- Computer Science Logic
- Metafinite model theory
- An analysis of fixed-point queries on binary trees
- A Step Up in Expressiveness of Decidable Fixpoint Logics
- Relational queries computable in polynomial time
- Title not available (Why is that?)
- Some Turing-complete extensions of first-order logic
- Title not available (Why is that?)
- LATIN 2004: Theoretical Informatics
- How to define a linear order on finite models
- Semantic restrictions over second-order logic
- Mathematical Foundations of Computer Science 2005
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- Title not available (Why is that?)
- On the expressive power of counting
- Title not available (Why is that?)
This page was built for publication: The expressive power of fixed-point logic with counting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4879905)
