Advice Automatic Structures and Uniformly Automatic Classes

DOI10.4230/LIPICS.CSL.2017.35zbMATH Open1434.03099OpenAlexW2741171410MaRDI QIDQ5111205FDOQ5111205

Frederic Reinhardt, Faried Abu Zaid, Erich Grädel

Publication date: 26 May 2020

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

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
• scientific article; zbMATH DE number 7533328
• Analysing Complexity in Classes of Unary Automatic Structures
• Model-theoretic complexity of automatic structures
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES

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)

Cited In (9)

• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Decidability for Sturmian words
• On the Complexity of Infinite Advice Strings
• 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
• 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)