DOI

A binary language-theoretic operation is proposed, which is dual to the concatenation of languages in the same sense as the universal quantifier in logic is dual to the existential quantifier; the dual of Kleene star is defined accordingly. These operations arise whenever concatenation or star appear in the scope of negation. The basic properties of the new operations are determined in the paper. Their use in regular expressions and in language equations is considered, and it is shown that they often eliminate the need of using negation, at the same time having an important technical advantage of being monotone. A generalization of context-free grammars featuring dual concatenation is introduced and proved to be equivalent to the recently studied Boolean grammars.

Язык оригиналаанглийский
Страницы (с-по)425-447
Число страниц23
ЖурналTheoretical Computer Science
Том345
Номер выпуска2-3
DOI
СостояниеОпубликовано - 22 ноя 2005
Опубликовано для внешнего пользованияДа

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

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

ID: 41141012