Climbing up the elementary complexity classes with theories of automatic structures

DOI10.4230/LIPICS.CSL.2018.3MaRDI QIDQ5079723FDOQ5079723

Authors: Peter Lindner, Dietrich Kuske 

Publication date: 28 May 2022

Recommendations

• Automatic structures of bounded degree
• Theories of Automatic Structures and Their Complexity
• Model Theoretic Complexity of Automatic Structures (Extended Abstract)
• Model-theoretic complexity of automatic structures
• Automatic structures of bounded degree revisited

zbMATH Keywords

complexity theoryautomatic structuresmodel theory

Mathematics Subject Classification ID

Logic in computer science (03B70)

Cites Work

• On direct products of automaton decidable theories
• Parametrized complexity theory.
• Three lectures on automatic structures
• Automata Presenting Structures: A Survey of the Finite String Case
• STACS 2004
• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• An application of games to the completeness problem for formalized theories
• Decision Problems of Finite Automata Design and Related Arithmetics
• The complexity of first-order and monadic second-order logic revisited
• The complexity of logical theories
• The first order properties of products of algebraic systems
• Synchronized rational relations of finite and infinite words
• The computational complexity of logical theories
• Automatic structures of bounded degree revisited
• Unary automatic graphs: an algorithmic perspective
• Title not available (Why is that?)
• Automata-based presentations of infinite structures
• Some natural decision problems in automatic graphs
• Theories of Automatic Structures and Their Complexity

Cited In (2)

• Title not available (Why is that?)
• Advice Automatic Structures and Uniformly Automatic Classes

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)