The omega-inequality problem for concatenation hierarchies of star-free languages

Autoři

ALMEIDA Jorge KLÍMA Ondřej KUNC Michal

Druh Článek v odborném periodiku
Časopis / Zdroj Forum Mathematicum
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
WWW https://www.degruyter.com/view/j/form.ahead-of-print/forum-2016-0028/forum-2016-0028.xml
Doi http://dx.doi.org/10.1515/forum-2016-0028
Klíčová slova Pseudovariety; relatively free profinite semigroup; ordered monoid; concatenation hierarchy; Straubing–Thérien hierarchy
Popis The problem considered in this paper is whether an inequality of omega-terms is valid in a given level of a concatenation hierarchy of star-free languages. The main result shows that this problem is decidable for all (integer and half) levels of the Straubing-Therien hierarchy.
Související projekty:

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