The expressive power of fixed-point logic with counting
From MaRDI portal
Publication:4879905
Recommendations
Cites work
- An optimal lower bound on the number of variables for graph identification
- Datalog extensions for database queries and updates
- Fixed-point extensions of first-order logic
- Infinitary logic and inductive definability over finite structures
- Infinitary logics and 0-1 laws
- Relational queries computable in polynomial time
- Upper and lower bounds for first order expressibility
Cited in
(50)- scientific article; zbMATH DE number 1954377 (Why is no real title available?)
- Metafinite model theory
- Capturing the polynomial hierarchy by second-order revised Krom logic
- Implicit definability and infinitary logic in finite model theory (extended abstract)
- Counting on CTL^*: On the expressive power of monadic path logic
- Rank logic is dead, long live rank logic!
- Cardinality logics. I: Inclusions between languages based on ``exactly
- Adding for-loops to first-order logic
- Canonization for two variables and puzzles on the square
- Fixed-point logics and computation
- 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
- The Power of Counting Logics on Restricted Classes of Finite Structures
- Logics with aggregate operators
- 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
- scientific article; zbMATH DE number 515730 (Why is no real title available?)
- 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
- Metafinite model theory
- Computer Science Logic
- An analysis of fixed-point queries on binary trees
- A Step Up in Expressiveness of Decidable Fixpoint Logics
- Relational queries computable in polynomial time
- scientific article; zbMATH DE number 4009811 (Why is no real title available?)
- Some Turing-complete extensions of first-order logic
- scientific article; zbMATH DE number 139633 (Why is no real title available?)
- How to define a linear order on finite models
- LATIN 2004: Theoretical Informatics
- Semantic restrictions over second-order logic
- Mathematical Foundations of Computer Science 2005
- scientific article; zbMATH DE number 515737 (Why is no real title available?)
- scientific article; zbMATH DE number 1670476 (Why is no real title available?)
- scientific article; zbMATH DE number 979011 (Why is no real title available?)
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- scientific article; zbMATH DE number 4008383 (Why is no real title available?)
- On the expressive power of counting
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)
