Informace o publikaci

Hierarchies of piecewise testable languages

Logo poskytovatele
Název česky Hierarchie po částech testovatelných jazyků
Autoři

KLÍMA Ondřej POLÁK Libor

Rok publikování 2008
Druh Článek ve sborníku
Konference Developments in Language Theory
Fakulta / Pracoviště MU

Přírodovědecká fakulta

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info