Transducers and the decidability of independence in free monoids

DOI10.1016/0304-3975(94)90281-XzbMath0938.68710MaRDI QIDQ1341744

Kai Salomaa, Helmut Jürgensen, Sheng Yu

Publication date: 27 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

FORMAL DESCRIPTIONS OF CODE PROPERTIES: DECIDABILITY, COMPLEXITY, IMPLEMENTATION ⋮ Codes defined by multiple sets of trajectories ⋮ Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions ⋮ Language equations, maximality and error-detection ⋮ Decidability of code properties ⋮ Dependences related to strict binary relations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Look-ahead on pushdowns
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Pushdown machines for the macro tree transducer
• High level tree transducers and iterated pushdown tree transducers
• The IO- and OI-hierarchies
• Iterated stack automata and complexity classes
• Languages whose \(n\)-element subsets are codes
• IO and OI. I
• Anti-commutative languages and n-codes
• Checking automata and one-way stack languages
• An automata-theoretical characterization of the OI-hierarchy
• Relations on free monoids, their independent sets, and codes¹
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• n-Prefix–suffix languages^∗
• Indexed Grammars—An Extension of Context-Free Grammars
• Preservation of languages by transducers
• Full AFLs and nested iterated substitution

This page was built for publication: Transducers and the decidability of independence in free monoids