Climbing up the elementary complexity classes with theories of automatic structures
From MaRDI portal
Recommendations
Cites work
- A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
- An application of games to the completeness problem for formalized theories
- Automata Presenting Structures: A Survey of the Finite String Case
- Automata-based presentations of infinite structures
- Automatic structures of bounded degree revisited
- Decision Problems of Finite Automata Design and Related Arithmetics
- scientific article; zbMATH DE number 6678444 (Why is no real title available?)
- On direct products of automaton decidable theories
- Parametrized complexity theory.
- Some natural decision problems in automatic graphs
- STACS 2004
- Synchronized rational relations of finite and infinite words
- The complexity of first-order and monadic second-order logic revisited
- The complexity of logical theories
- The computational complexity of logical theories
- The first order properties of products of algebraic systems
- Theories of Automatic Structures and Their Complexity
- Three lectures on automatic structures
- Unary automatic graphs: an algorithmic perspective
Cited in
(3)
This page was built for publication: Climbing up the elementary complexity classes with theories of automatic structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5079723)
