Analysing Complexity in Classes of Unary Automatic Structures

DOI10.1007/978-3-642-00982-2_44zbMath1234.68226OpenAlexW1499975475MaRDI QIDQ3618610

Mia Minnes, Jiamou Liu

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

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

Related Items (2)

The isomorphism problem on classes of automatic structures with transitive relations ⋮ Complexity and categoricity of injection structures induced by finite state transducers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• On direct products of automaton decidable theories
• Finite presentations of infinite structures: Automata and interpretations
• Three Lectures on Automatic Structures
• Model Theoretic Complexity of Automatic Structures (Extended Abstract)
• Unary Automatic Graphs: An Algorithmic Perspective
• Automata Presenting Structures: A Survey of the Finite String Case
• STACS 2004
• Automatic Structures: Richness and Limitations
• Database Theory - ICDT 2005

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