Shuffle on positive varieties of languages
| Autor: | Jean-Eric Pin, Antonio Cano Gómez |
|---|---|
| Přispěvatelé: | Departamento de Sistemas Informáticos y Computación [Valencia], Universitat Politècnica de València (UPV), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Pin, Jean-Eric |
| Jazyk: | angličtina |
| Předmět: |
General Computer Science
shuffle Finite Automata Inverse Class (philosophy) Minimal ideal 0102 computer and information sciences [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences regular language Theoretical Computer Science Combinatorics Morphism Regular language Ordered semigroups 0101 mathematics MR 68Q45 (20M35) Mathematics Discrete mathematics Varieties shuffle 010102 general mathematics finite semigroup Decidability variety [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] 010201 computation theory & mathematics Languages Variety (universal algebra) Element (category theory) Computer Science(all) |
| Zdroj: | Theoretical Computer Science Theoretical Computer Science, Elsevier, 2004, 312, pp.433-461 |
| ISSN: | 0304-3975 1879-2294 |
| DOI: | 10.1016/j.tcs.2003.10.034 |
| Popis: | We show there is a unique maximal positive variety of languages which does not contain the language (ab)*. This variety is the unique maximal positive variety satisfying the two following conditions: it is strictly included in the class of rational languages and is closed under the shuffle operation. It is also the unique maximal proper positive variety closed under length preserving morphims. The ordered monoids of the corresponding variety of ordered monoids are characterized as follows: for every pair (a, b) of mutually inverse elements, and for every element z of the minimal ideal of the submonoid generated by a and b, (abzab)^ω ≤ ab. In particular this variety is decidable. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|