It was recently found that concatenation of formal languages has a logical dual (A. Okhotin, The dual of concatenation, Theoret. Comput. Sci., 345 (2005), 425-447). 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.

Original languageEnglish
Pages (from-to)1361-1370
Number of pages10
JournalInternational Journal of Foundations of Computer Science
Volume18
Issue number6
DOIs
StatePublished - 1 Dec 2007

    Scopus subject areas

  • Computer Science (miscellaneous)

    Research areas

  • Concatenation, Conjunctive grammars, Language equations

ID: 41141553