Homomorphisms preserving deterministic context-free languages

Tommi Lehtinen, Alexander Okhotin

Результат исследований: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)1049-1066
Число страниц18
ЖурналInternational Journal of Foundations of Computer Science
Том24
Номер выпуска7
DOI
СостояниеОпубликовано - 1 ноя 2013

Предметные области Scopus

  • Компьютерные науки (разное)

Fingerprint Подробные сведения о темах исследования «Homomorphisms preserving deterministic context-free languages». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать