Analysing Complexity in Classes of Unary Automatic Structures

DOI10.1007/978-3-642-00982-2_44MaRDI QIDQ3618610zbMATH OpenOpenAlexFDO

Authors Jiamou Liu, Mia Minnes

Publication date 2 April 2009

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10292/2810

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Deciding the isomorphism problem in classes of unary automatic structures
• Automatic structures of bounded degree
• The isomorphism problem on classes of automatic structures with transitive relations
• Theories of Automatic Structures and Their Complexity
• Automatic Structures: Richness and Limitations

Cites work

• Automata Presenting Structures: A Survey of the Finite String Case
• Automatic Structures: Richness and Limitations
• Database Theory - ICDT 2005
• Elements of finite model theory.
• Finite presentations of infinite structures: Automata and interpretations
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 1747445 (Why is no real title available?)
• scientific article; zbMATH DE number 2182451 (Why is no real title available?)
• scientific article; zbMATH DE number 5041651 (Why is no real title available?)
• Model Theoretic Complexity of Automatic Structures (Extended Abstract)
• On direct products of automaton decidable theories
• STACS 2004
• Three lectures on automatic structures
• Unary Automatic Graphs: An Algorithmic Perspective

Cited in

(6)

• Complexity and categoricity of injection structures induced by finite state transducers
• Deciding the isomorphism problem in classes of unary automatic structures
• The isomorphism problem on classes of automatic structures with transitive relations
• Uniformly Automatic Classes of Finite Structures
• Advice Automatic Structures and Uniformly Automatic Classes
• scientific article; zbMATH DE number 5041651 (Why is no real title available?)

This page was built for publication: Analysing Complexity in Classes of Unary Automatic Structures

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