A note on morphic characterization of languages

DOI10.1016/0166-218X(83)90045-8MaRDI QIDQ1171887zbMATH OpenOpenAlexFDO

Authors 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

regular languagecontext-free languagerecursively enumerable languagesDyck languagerational transductionshomomorphic characterizationtwin- shuffle language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3673546 (Why is no real title available?)
• scientific article; zbMATH DE number 3767067 (Why is no real title available?)
• scientific article; zbMATH DE number 3633742 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• A homomorphic characterization of regular languages
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• The Hardest Context-Free Language

Cited in

(18)

• 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
• A characterization of recognizable picture languages by tilings by finite sets
• Identities and transductions
• Compositional representation of rational functions
• Two characterizations of rational adherences
• On the leftmost derviation in matrix grammars
• Bifaithful starry transductions
• On characterisation of language families in terms of inverse morphisms
• Finite transducers and rational transductions
• scientific article; zbMATH DE number 3970124 (Why is no real title available?)
• Deterministic sequential functions
• Decidability problems for unary output sequential transducers
• Representation of rational functions with prefix and suffix codings
• Inverse morphic equivalence on languages
• A new normal form for the compositions of morphisms and inverse morphisms
• The three subfamilies of rational \(\omega\)-languages closed under \(\omega\)-transduction

This page was built for publication: A note on morphic characterization of languages

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