Hierarchies of piecewise testable languages
| Název česky | Hierarchie po částech testovatelných jazyků |
|---|---|
| Autoři | |
| Rok publikování | 2008 |
| Druh | Článek ve sborníku |
| Konference | Developments in Language Theory |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Obecná matematika |
| Klíčová slova | varieties of languages; piecewise testable languages; syntactic monoid |
| Popis | Třída jazyků, které jsou Boolovskou kombinací jazyků tvaru $A^*a_1A^*a_2A^*\dots A^*a_\ell A^*$, kde $a_1,\dots, a_\ell\in A,\ell\le k$, pro pevně zvolené $k\ge 0$, tvoří hierarchii po částech testovalených jazyků. Tyto jazyky studovali Simon, Blanchet-Sadri, Volkov a další. Hlavní otázkou byla existence konečné báze identit pro odpovídající pseudovariety monoidů a generující monoidy pro tyto třídy. V tomto příspěvku se zabýváme podobnými otazkami v případě konečných sjednocení a pozitivních Boolovských kombinací popsaných jazyků. V prvním případě jsou odpovídající pseudovariety dány jednou identitou, v druhém případě existují konečné báze pro $k$ rovno 1 a 2 a neexistují konečné báze pro $k\ge 4$ (případ $k=3$ zůstává nevyřešen). Všechny studované pseudovariety lze generovat jednou algebraickou strukturou. |
| Související projekty: |