Some operations and transductions that preserve rationality
Pin, Jean-Eric ; Sakarovitch, Jacques
HAL, hal-00340780 / Harvested from HAL
We give a unified framework to treat the following problem. Let (L_1, ..., L_n) → f(L_1, ..., L_n) be an operation on languages. Given monoids recognizing the languages L_1, ..., L_n, give an explicit construction of a monoid recognizing f(L_1, ..., L_n). Our method gives in particular a simple way to prove that an operation preserves rational languages. The scope of our method is quite broad and goes from classical operations such as union, intersection, concatenation, quotient, shuffle, inverse and direct morphisms, etc., to less classical ones such as infiltration, Dyck reduction, longest common prefix, Straubing's counting, etc. It includes also questions that are not expressed directly as operations on languages, as, for example, Reutenauer's theorem on TOL-systems. The key idea of our construction is to consider an operation as the inverse of a transduction.
Publié le : 1983-07-05
Classification:  regular language,  recognizable,  rational,  transduction,  [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH],  [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],  [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT],  [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR]
@article{hal-00340780,
     author = {Pin, Jean-Eric and Sakarovitch, Jacques},
     title = {Some operations and transductions that preserve rationality},
     journal = {HAL},
     volume = {1983},
     number = {0},
     year = {1983},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00340780}
}
Pin, Jean-Eric; Sakarovitch, Jacques. Some operations and transductions that preserve rationality. HAL, Tome 1983 (1983) no. 0, . http://gdmltest.u-ga.fr/item/hal-00340780/