Computing topological closures through algebraic recognition.

Room FC1.006, DMat-FCUP
Friday, 3 March, 2017 (All day)

One of the key problems that has been considered on a pseudovariety V of finite monoids consists in deciding whether a given finite system of equations with rational constraints has a solution in every monoid from V. An instance of this problem is the separation problem, which has received considerable attention lately due to its role in investigations on the Straubing-Thérien hierarchy of star-free languages.

 

A technique that emerged about 20 years ago to deal with such problems consists in finding an enriched language for monoids in which uniform solutions for such systems may be expressed but such that the enriched language remains under control, so that, in particular, the corresponding word problem is decidable in V-free algebras in the enriched language. This property, which is known as tameness for the systems of equations of interest, entails decidability of the original problem since, under simple assumptions, one may enumerate in parallel all positive and all negative instances of the problem. In other words, tameness yields "theoretical decidability" of the original problem, which opens the path to finding practical algorithms for solving the original problem.

 

Intimately connected with tameness is the calculation of the topological closure of a rational language in the V-free algebra in the enriched language. The purpose of this talk is to show how such closures turn out be effectively computable recognizable subsets for the pseudovarieties R and DA, of all finite respectively R-trivial monoids and monoids in which all regular elements are idempotents. This yields effective solutions of the original problem for these pseudovarieties for many systems of equations of interest.

 

(Based on joint work with J. C. Costa and M. Zeitoun, and with M. Kufleitner.)

Speaker: 

Jorge Almeida

Institution: 

FCUP-CMUP
Error | CMUP

Error

The website encountered an unexpected error. Please try again later.