Injection Structures Specified by Finite State Transducers

DOI10.1007/978-3-319-50062-1_24MaRDI QIDQ2970970zbMATH OpenOpenAlexFDO

Authors Douglas Cenzer, Mia Minnes, Samuel R. Buss, Jeffrey Remmel

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

automatic structurescomputability theoryfinite state automatafinite state transducersinjection structures

Mathematics Subject Classification ID

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

Recommendations

• Complexity of injection structures induced by finite state transducers
• Complexity and categoricity of injection structures induced by finite state transducers
• Inference of finite-state transducers from regular languages
• scientific article; zbMATH DE number 3952037
• Finite state transducers
• scientific article; zbMATH DE number 1670708
• scientific article; zbMATH DE number 4201646
• Injective envelopes of transition systems and Ferrers languages
• On injectivity of deterministic top-down tree transducers
• Finite state transducers with predicates and identities

Cites work

• Automatic linear orders and trees
• Automatic Structures: Richness and Limitations
• Automaticity of ordinals and of homogeneous graphs
• Computability-theoretic properties of injection structures
• Computable structures and the hyperarithmetical hierarchy
• Effective Categoricity of Injection Structures
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• Logical Reversibility of Computation
• On direct products of automaton decidable theories
• STACS 2004
• Unary Automatic Graphs: An Algorithmic Perspective

Cited in

(5)

• Complexity and categoricity of injection structures induced by finite state transducers
• The isomorphism problem for FST injection structures
• Effective categoricity of automatic equivalence and nested equivalence structures
• Injective envelopes of transition systems and Ferrers languages
• Complexity of injection structures induced by finite state transducers

This page was built for publication: Injection Structures Specified by Finite State Transducers

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