Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs
From MaRDI portal
Publication:3586010
DOI10.1007/978-3-642-15025-8_17zbMath1287.68064arXiv1001.2572OpenAlexW2963086889MaRDI QIDQ3586010
Publication date: 3 September 2010
Published in: Fields of Logic and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1001.2572
Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finite model theory and its applications.
- Elements of finite model theory.
- Procedural languages for database queries and updates
- The strong perfect graph theorem
- Fixed-point extensions of first-order logic
- Choiceless polynomial time
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- An optimal lower bound on the number of variables for graph identification
- An extension of fixpoint logic with a symmetry-based choice construct
- A restricted second order logic for finite structures
- On highly closed cellular algebras and highly closed isomorphisms
- On a new high dimensional Weisfeiler-Lehman algorithm
- Canonization for two variables and puzzles on the square
- Definability hierarchies of generalized quantifiers
- Structure and complexity of relational queries
- Expressive equivalence of least and inflationary fixed-point logic
- The expressive power of finitely many generalized quantifiers
- On logics with two variables
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- Upper bounds to the clique width of graphs
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Approximating clique-width and branch-width
- Almost Everywhere Equivalence of Logics in Finite Model Theory
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- From Invariants to Canonization in Parallel
- Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
- Testing Graph Isomorphism in Parallel by Playing a Game
- Relational queries computable in polynomial time
- Languages that Capture Complexity Classes
- Generalized Quantifiers and Logical Reducibilities
- On polynomial time computation over unordered structures
- Computer Science Logic
- Fixed-point definability and polynomial time on graphs with excluded minors
- Characterizations of derived graphs
- Sequential abstract-state machines capture sequential algorithms
