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.

Original languageEnglish
Pages (from-to)425-447
Number of pages23
JournalTheoretical Computer Science
Volume345
Issue number2-3
DOIs
StatePublished - 22 Nov 2005
Externally publishedYes

    Research areas

  • Boolean grammars, Co-context-free languages, Conjunctive grammars, Deductive parsing, Formal languages, Language equations, Regular expressions, Semiring

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 41141012