scientific article; zbMATH DE number 5041651

MaRDI QIDQ5476782zbMATH OpenFDO

Authors N. S. Vinokurov

Publication date 18 July 2006

Full work available at URL https://eudml.org/doc/52660, http://www.emis.de/journals/SMZ/2005/01/71.htm

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

automatic automorphismautomatic structureembeddability problemfinite automatonisomorphism problem

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Recommendations

• Theories of Automatic Structures and Their Complexity
• On the complexity of automatic complexity
• Model-theoretic complexity of automatic structures
• Model Theoretic Complexity of Automatic Structures (Extended Abstract)
• Complexity of some problems from the theory of automata
• Climbing up the elementary complexity classes with theories of automatic structures
• scientific article; zbMATH DE number 2087550
• Analysing Complexity in Classes of Unary Automatic Structures
• Automatic Structures: Richness and Limitations

Cited in

(7)

• The isomorphism problem on classes of automatic structures with transitive relations
• Automated complexity analysis based on ordered resolution
• The complexity of \(\mathit{AUTOSAT}(\Sigma^i_m)\)
• Some natural decision problems in automatic graphs
• Analysing Complexity in Classes of Unary Automatic Structures
• scientific article; zbMATH DE number 4041268 (Why is no real title available?)
• Index sets of classes of automatic structures

This page was built for publication:

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