Language equations with complementation: Expressive power

Alexander Okhotin, Oksana Yakimova

Результат исследований: Научные публикации в периодических изданияхстатья

6 Цитирования (Scopus)


Consider a system of language equations of the form Xi= φi( X1,..., Xn)(1in), where every φi may contain the operations of concatenation and complementation. These systems have been studied in "Language equations with complementation: Decision problems" [A. Okhotin, O. Yakimova, Theoretical Computer Science 376 (2007) 112126]. This paper investigates the family of languages representable by unique solutions of such systems. A method for proving nonrepresentability of particular languages is developed. Several natural subfamilies of this family are compared to each other and to the main known families of formal languages. Their position in the hierarchy is established.

Язык оригиналаанглийский
Страницы (с-по)71-86
Число страниц16
ЖурналTheoretical Computer Science
СостояниеОпубликовано - 27 янв 2012

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

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

Fingerprint Подробные сведения о темах исследования «Language equations with complementation: Expressive power». Вместе они формируют уникальный семантический отпечаток (fingerprint).