Injection Structures Specified by Finite State Transducers

DOI10.1007/978-3-319-50062-1_24zbMath1485.03108OpenAlexW2559451524MaRDI QIDQ2970970

Douglas Cenzer, Mia Minnes, Jeffery B. Remmel, Samuel R. Buss

Publication date: 4 April 2017

Published in: Computability and Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-50062-1_24

zbMATH Keywords

computability theoryautomatic structuresfinite state automatafinite state transducersinjection structures

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Computable structure theory, computable model theory (03C57)

Related Items

The isomorphism problem for FST injection structures, Effective categoricity of automatic equivalence and nested equivalence structures, Complexity and categoricity of injection structures induced by finite state transducers

Cites Work

• Unnamed Item
• On direct products of automaton decidable theories
• Computable structures and the hyperarithmetical hierarchy
• Automaticity of ordinals and of homogeneous graphs
• Computability-theoretic properties of injection structures
• Effective Categoricity of Injection Structures
• Unary Automatic Graphs: An Algorithmic Perspective
• Automatic linear orders and trees
• STACS 2004
• Automatic Structures: Richness and Limitations
• Logical Reversibility of Computation