DOI

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.

Язык оригиналаанглийский
Страницы (с-по)1361-1370
Число страниц10
ЖурналInternational Journal of Foundations of Computer Science
Том18
Номер выпуска6
DOI
СостояниеОпубликовано - 1 дек 2007

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

  • Компьютерные науки (разное)

ID: 41141553