A note on morphic characterization of languages

DOI10.1016/0166-218X(83)90045-8zbMath0499.68031MaRDI QIDQ1171887

Juhani Karhumäki, Matti Linna

Publication date: 1983

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(83)90045-8

zbMATH Keywords

context-free language; regular language; recursively enumerable languages; Dyck language; rational transductions; homomorphic characterization; twin- shuffle language

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS, Identities and transductions, A Kleene characterization of computability, The three subfamilies of rational \(\omega\)-languages closed under \(\omega\)-transduction, Inverse morphic equivalence on languages, On purely morphic characterizations of context-free languages, Representations of language families by homomorphic equality operations and generalized equality sets, Bifaithful starry transductions, Decidability problems for unary output sequential transducers, A characterization of recognizable picture languages by tilings by finite sets, Deterministic sequential functions, Representation of rational functions with prefix and suffix codings, Two characterizations of rational adherences, Finite transducers and rational transductions, On characterisation of language families in terms of inverse morphisms, Unnamed Item, A new normal form for the compositions of morphisms and inverse morphisms, Compositional representation of rational functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A homomorphic characterization of regular languages
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• The Hardest Context-Free Language