Complexity and categoricity of injection structures induced by finite state transducers

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

Authors Richard Krogman, Douglas Cenzer

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

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

Cited in

(3)

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

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)