Open problems on regular languages: an historical perspectiveReportar como inadecuado

Open problems on regular languages: an historical perspective - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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

Autor: Laura Chaubard - Jean-Eric Pin -



Documentos relacionados