Uniformly Automatic Classes of Finite Structures

DOI10.4230/LIPICS.FSTTCS.2018.10OpenAlexW2907647026MaRDI QIDQ5090943FDOQ5090943

Authors:

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.10

Recommendations

• Analysing Complexity in Classes of Unary Automatic Structures
• Advice Automatic Structures and Uniformly Automatic Classes
• Automatic structures of bounded degree revisited
• Climbing up the elementary complexity classes with theories of automatic structures
• Automatic Structures: Richness and Limitations

zbMATH Keywords

model checkingautomatic structuresfixed-parameter tractabilityalgorithmic meta theorems

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites Work

• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Linear time solvable optimization problems on graphs of bounded clique-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Title not available (Why is that?)
• Transforming structures by set interpretations
• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• An application of games to the completeness problem for formalized theories
• Sur l'extension aux relations de quelques propriétés des ordres
• Title not available (Why is that?)
• The computational complexity of logical theories
• Automatic structures of bounded degree revisited
• Evaluation of an MSO-Solver
• Advice Automatic Structures and Uniformly Automatic Classes
• Upper Bounds on the Automata Size for Integer and Mixed Real and Integer Linear Arithmetic (Extended Abstract)
• Ehrenfeucht-Fraïssé goes automatic for real addition
• Title not available (Why is that?)
• A faster parameterized algorithm for treedepth
• Factoring Groups Efficiently
• Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree
• First-order queries on finite abelian groups

Cited In (3)

• EQUIVALENT AUTOMATIC STRUCTURES AND THEIR BOUNDARIES
• Automatic structures of bounded degree revisited
• Advice Automatic Structures and Uniformly Automatic Classes

This page was built for publication: Uniformly Automatic Classes of Finite Structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090943)