Open problems on regular languages: an historical perspectiveReport as inadecuate

Open problems on regular languages: an historical perspective - Download this document for free, or read online. Document in PDF available to download.

1 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications

Abstract : Operations on regular languages have been studied for fifty years, but several major problems remain wide open. This paper surveys the semigroup approach to these problems. We consider successively the star-height problem, the Straubing-Thérien-s concatenation hierarchy and the shuffle operation. On the algebraic side, we present Eilenberg-s variety theory and its successive improvements, including the recent notion of C-variety.

Keywords : regular languages operations on languages concatenation hierarchy shuffle star-height C-variety

Author: Laura Chaubard - Jean-Eric Pin -



Related documents