A note on morphic characterization of languages
From MaRDI portal
Publication:1171887
DOI10.1016/0166-218X(83)90045-8zbMath0499.68031OpenAlexW1969798715MaRDI QIDQ1171887
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
context-free languageregular languagerecursively enumerable languagesDyck languagerational transductionshomomorphic characterizationtwin- shuffle language
Related Items (18)
Representation of rational functions with prefix and suffix codings ⋮ A Kleene characterization of computability ⋮ On purely morphic characterizations of context-free languages ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ Bifaithful starry transductions ⋮ Compositional representation of rational functions ⋮ Identities and transductions ⋮ A new normal form for the compositions of morphisms and inverse morphisms ⋮ The three subfamilies of rational \(\omega\)-languages closed under \(\omega\)-transduction ⋮ Decidability problems for unary output sequential transducers ⋮ On characterisation of language families in terms of inverse morphisms ⋮ Unnamed Item ⋮ Two characterizations of rational adherences ⋮ Finite transducers and rational transductions ⋮ A characterization of recognizable picture languages by tilings by finite sets ⋮ ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS ⋮ Inverse morphic equivalence on languages ⋮ Deterministic sequential functions
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A note on morphic characterization of languages
