Automatic Structures: Richness and Limitations

DOI10.2168/LMCS-3(2:2)2007zbMath1128.03028OpenAlexW3099901893MaRDI QIDQ5310687

Sasha Rubin, Bakhadyr Khoussainov, André Nies, Frank Stephan

Publication date: 11 October 2007

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2168/lmcs-3(2:2)2007

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Computable structure theory, computable model theory (03C57)

Related Items

Tree-automatic scattered linear orders ⋮ Pumping for ordinal-automatic structures1 ⋮ Automata model for verifying attibuted-based access control policy in systems with a finite number of objects ⋮ The isomorphism problem for FST injection structures ⋮ Automatic models of first order theories ⋮ Word automatic groups of nilpotency class 2 ⋮ Unary Automatic Graphs: An Algorithmic Perspective ⋮ Effective categoricity of automatic equivalence and nested equivalence structures ⋮ The complexity of recursive constraint satisfaction problems ⋮ Injection Structures Specified by Finite State Transducers ⋮ Isomorphisms of scattered automatic linear orders ⋮ On automaton presentations of projective planes ⋮ A hierarchy of tree-automatic structures ⋮ Isomorphism of Regular Trees and Words ⋮ Algebraic structures computable without delay ⋮ Model-theoretic properties of \(\omega\)-automatic structures ⋮ Eliminating unbounded search in computable algebra ⋮ The isomorphism relation between tree-automatic structures ⋮ From automatic structures to automatic groups. ⋮ Ehrenfeucht-Fraïssé goes automatic for real addition ⋮ The back-and-forth method and computability without delay ⋮ Automata and Answer Set Programming ⋮ Learners based on transducers ⋮ Tree-Automatic Well-Founded Trees ⋮ Path Feasibility Analysis for String-Manipulating Programs ⋮ AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES ⋮ Analysing Complexity in Classes of Unary Automatic Structures ⋮ Semi-synchronous transductions ⋮ Where Automatic Structures Benefit from Weighted Automata ⋮ The isomorphism problem on classes of automatic structures with transitive relations ⋮ Complexity and categoricity of injection structures induced by finite state transducers

This page was built for publication: Automatic Structures: Richness and Limitations