Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
From MaRDI portal
Publication:2478545
DOI10.1016/j.apal.2007.11.011zbMath1136.03024DBLPjournals/apal/DawarRR08OpenAlexW2055008899WikidataQ58215577 ScholiaQ58215577MaRDI QIDQ2478545
Anuj Dawar, Benjamin Rossman, David Richerby
Publication date: 28 March 2008
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2007.11.011
Related Items (10)
On symmetric circuits and fixed-point logics ⋮ Symbioses between mathematical logic and computer science ⋮ Choiceless Polynomial Time on Structures with Small Abelian Colour Classes ⋮ Is Polynomial Time Choiceless? ⋮ Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs ⋮ Database Theory, Yuri, and Me ⋮ Choiceless Computation and Symmetry ⋮ A Natural Axiomatization of Computability and Proof of Church's Thesis ⋮ Choiceless Logarithmic Space ⋮ Computation on structures. Behavioural theory, logic, complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-point extensions of first-order logic
- Choiceless polynomial time
- Infinitary logics and 0-1 laws
- An optimal lower bound on the number of variables for graph identification
- An extension of fixpoint logic with a symmetry-based choice construct
- Logical hierarchies in PTIME
- Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
- Relational queries computable in polynomial time
- Fixed-point Logics with Nondeterministic Choice
- On fixed-point logic with counting
- On polynomial time computation over unordered structures
- Evolving Algebras 1993: Lipari Guide
- Computer Science Logic
This page was built for publication: Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
