TY - JOUR

T1 - Homomorphisms preserving deterministic context-free languages

AU - Lehtinen, Tommi

AU - Okhotin, Alexander

PY - 2013/11/1

Y1 - 2013/11/1

N2 - The paper characterizes the family of homomorphisms, under which the deterministic context-free languages, the LL context-free languages and the unambiguous context-free languages are closed. The family of deterministic context-free languages is closed under a homomorphism h if and only if h is either a code of bounded deciphering delay, or the images of all symbols under h are powers of the same string. The same characterization holds for LL context-free languages. The unambiguous context-free languages are closed under h if and only if either h is a code, or the images of all symbols under h are powers of the same string.

AB - The paper characterizes the family of homomorphisms, under which the deterministic context-free languages, the LL context-free languages and the unambiguous context-free languages are closed. The family of deterministic context-free languages is closed under a homomorphism h if and only if h is either a code of bounded deciphering delay, or the images of all symbols under h are powers of the same string. The same characterization holds for LL context-free languages. The unambiguous context-free languages are closed under h if and only if either h is a code, or the images of all symbols under h are powers of the same string.

KW - Bounded deciphering delay

KW - Closure properties

KW - Coding theory

KW - Context-free grammars

UR - http://www.scopus.com/inward/record.url?scp=84897633833&partnerID=8YFLogxK

U2 - 10.1142/S0129054113400303

DO - 10.1142/S0129054113400303

M3 - Article

AN - SCOPUS:84897633833

VL - 24

SP - 1049

EP - 1066

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 7

ER -