Non-erasing variants of the Chomsky-Schützenberger theorem

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

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

Аннотация

The famous theorem by Chomsky and Schützenberger ("The algebraic theory of context-free languages", 1963) states that every context-free language is representable as h(D k ∩ R), where D k is the Dyck language over k ≥ pairs of brackets, R is a regular language and h is a homomorphism. This paper demonstrates that one can use a non-erasing homomorphism in this characterization, as long as the language contains no one-symbol strings. If the Dyck language is augmented with neutral symbols, the characterization holds for every context-free language using a letter-to-letter homomorphism.

Язык оригиналаанглийский
Название основной публикацииDevelopments in Language Theory - 16th International Conference, DLT 2012, Proceedings
Страницы121-129
Число страниц9
DOI
СостояниеОпубликовано - 20 авг 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 Подробные сведения о темах исследования «Non-erasing variants of the Chomsky-Schützenberger theorem». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать