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

automatic structuresfirst-order logicabelian groupstorsion-free abelian groupsalgorithmic model theory

Mathematics Subject Classification ID

Model-theoretic algebra (03C60) Automata and formal grammars in connection with logical questions (03D05) Computable structure theory, computable model theory (03C57) 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)

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

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)