Homomorphisms preserving deterministic context-free languages

Tommi Lehtinen, Alexander Okhotin

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

1 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Название основной публикацииDevelopments in Language Theory - 16th International Conference, DLT 2012, Proceedings
Страницы154-165
Число страниц12
DOI
СостояниеОпубликовано - 2012
Опубликовано для внешнего пользованияДа
Событие16th International Conference on Developments in Language Theory, DLT 2012 - Taipei, Китайская Провинция Тайвань
Продолжительность: 14 авг 201217 авг 2012

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том7410 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция16th International Conference on Developments in Language Theory, DLT 2012
СтранаКитайская Провинция Тайвань
ГородTaipei
Период14/08/1217/08/12

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

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint

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

Цитировать