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

TitleThe omega-inequality problem for concatenation hierarchies of star-free languages
Publication TypePreprint
Year of Preprint2016
AuthorsAlmeida J., Klíma O., Kunc M.
Abstract

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-Thérien hierarchy.

[2016-2]

Area / Group: 

Semigroups, Automata and Languages