Advice Automatic Structures and Uniformly Automatic Classes

DOI10.4230/LIPICS.CSL.2017.35MaRDI QIDQ5111205zbMATH OpenOpenAlexFDO

Authors Faried Abu Zaid, Erich Grädel, Frederic Reinhardt

Publication date 26 May 2020

Full work available at URL https://dblp.uni-trier.de/db/conf/csl/csl2017.html#ZaidGR17

zbMATH Keywords

abelian groupsalgorithmic model theoryautomatic structuresfirst-order logictorsion-free abelian groups

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Model-theoretic algebra (03C60) Automata and formal grammars in connection with logical questions (03D05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Torsion-free groups, finite rank (20K15)

Recommendations

• Uniformly Automatic Classes of Finite Structures
• Advice hierarchies among finite automata
• Advice classes of parametrized tractability
• Deciding the isomorphism problem in classes of unary automatic structures
• STACS 2004
• Climbing up the elementary complexity classes with theories of automatic structures
• Analysing Complexity in Classes of Unary Automatic Structures
• Model-theoretic complexity of automatic structures
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES

Cited in

(11)

• Advice hierarchies among finite automata
• Second-order finite automata
• On the width of regular classes of finite structures
• Properties of a class of Toeplitz words
• The additive group of the rationals does not have an automatic presentation
• On the complexity of infinite advice strings
• Uniformly Automatic Classes of Finite Structures
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Automatic Structures: Richness and Limitations
• Decidability for Sturmian words
• Advice classes of parametrized tractability

This page was built for publication: Advice Automatic Structures and Uniformly Automatic Classes

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