Informace o publikaci
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: |