Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Notes on dual concatenation

Notes on dual concatenation

Alexander Okhotin, Notes on dual concatenation. TUCS Technical Reports 843, Turku Centre for Computer Science, 2007.

Abstract:

The concatenation of formal languages has a logical dual (A. Okhotin, <i>Theoret. Comput. Sci.</i>, 320 (2005), 425&#8722;447), which is particularly important in the study of Boolean operations in formal language theory. In this paper, the closure or nonclosure of common language families under dual concatenation with finite, co-finite and regular languages is determined. In addition, language equations with union, linear concatenation and dual concatenation with co-finite constants are shown to be almost equal in power to linear conjunctive grammars.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tOkhotin07c,
  title = {Notes on dual concatenation},
  author = {Okhotin, Alexander},
  number = {843},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2007},
  keywords = {Concatenation, conjunctive grammars, language equations, trellis automata},
  ISBN = {978-952-12-1962-7},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication