Complexity and categoricity of injection structures induced by finite state transducers

DOI10.1007/978-3-030-80049-9_10OpenAlexW3183007948MaRDI QIDQ2117771FDOQ2117771

Douglas Cenzer, Richard Krogman

Publication date: 22 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-80049-9_10

zbMATH Keywords

automatic structurescomputability theoryfinite state automatafinite state transducersinjection structures

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• On direct products of automaton decidable theories
• Automaticity of ordinals and of homogeneous graphs
• Automatic Structures: Richness and Limitations
• Model-theoretic complexity of automatic structures
• Generic copies of countable structures
• Deciding the isomorphism problem in classes of unary automatic structures
• Unary automatic graphs: an algorithmic perspective
• A general theory of translation
• \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures
• Automatic presentations of structures
• Computability-theoretic properties of injection structures
• Effective categoricity of automatic equivalence and nested equivalence structures
• Injection Structures Specified by Finite State Transducers
• Analysing Complexity in Classes of Unary Automatic Structures

Cited In (3)

• Complexity of injection structures induced by finite state transducers
• Injection Structures Specified by Finite State Transducers
• The isomorphism problem for FST injection structures

This page was built for publication: Complexity and categoricity of injection structures induced by finite state transducers

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