Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Seven families of language equ...

Seven families of language equations

Alexander Okhotin, Seven families of language equations. TUCS Technical Reports 844, Turku Centre for Computer Science, 2015.

Abstract:

Systems of equations of the form X_i = \phi_i(X_1, \ldots, X_n), for 1 <= i <= n, in which the unknowns X_i are formal languages, and the right-hand sides \phi_i may contain concatenation and union, are known for representing context-free grammars. If, instead of union only, another set of Boolean operations is used, the expressive power of such equations may change: for example, using both union and intersection leads to conjunctive grammars (Okhotin, 2001), whereas using all Boolean operations allows all recursive sets to be expressed by unique solutions (Okhotin, 2003). This paper investigates the expressive power of such equations with any possible set of Boolean operations. It is determined that different sets of Boolean operations give rise to exactly seven families of formal languages: the recursive languages, the conjunctive languages, the context-free languages, a certain family incomparable with the context-free languages, as well as three subregular families.

This paper is an extended version of an invited talk given at the AutoMathA 2007 conference held in Palermo, Italy on June 18--22, 2007.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tOkhotin07d,
  title = {Seven families of language equations},
  author = {Okhotin, Alexander},
  number = {844},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2015},
  ISBN = {978-952-12-1963-4},
}

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

Edit publication