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

**2016-01-29**

1601.08237 | math.GR

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\'erien hierarchy.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-05-24**

1905.10460 | math.GR

Given a regular language L, we effectively construct a unary semigroup that
recognizes the topologic… show more

**2019-04-17**

1904.08343 | math.GR

In this work we introduce a new succinct variant of the word problem in a
finitely generated group $… show more

**2015-11-05**

1511.01807 | cs.LO

The height of a piecewise-testable language $L$ is the maximum length of the
words needed to define … show more

**2019-03-25**

1903.10493 | math.GR

This paper studies the classes of semigoups and monoids with context-free and
deterministic context-… show more

**2018-04-24**

1804.08883 | cs.LO

For every class $\mathscr{C}$ of word languages, one may associate a decision
problem called $\maths… show more

**2017-11-15**

1711.05525 | math.GR

In algebraic terms, the insertion of $n$-powers in words may be modelled at
the language level by co… show more

**2019-04-05**

1904.04072 | math.AG

Given an ideal $I$ and a polynomial $f$ the {Ideal Membership Problem} is to
test if $f\in I$. This … show more

**2018-03-21**

1803.08019 | cs.LO

The subalgebra membership problem is the problem of deciding if a given
element belongs to an algebr… show more

**2019-01-08**

1901.02194 | cs.FL

We consider a language together with the subword relation, the cover
relation, and regular predicate… show more

**2017-12-22**

1712.08455 | cs.FL

The Eilenberg correspondence relates varieties of regular languages to
pseudovarieties of finite mon… show more

**2019-01-10**

1901.03361 | cs.FL

The dot-depth hierarchy of Brzozowski and Cohen classifies the star-free
languages of finite words. … show more

**2018-10-22**

1810.09287 | cs.FL

We investigate the complexity of the separation problem associated to classes
of regular languages. … show more

**2019-02-21**

1902.08048 | cs.LO

We consider algebras of languages over the signature of reversible Kleene
lattices, that is the regu… show more

**2018-10-06**

1810.02953 | cs.FL

We show that the shuffle $L \unicode{x29E2} F$ of a piecewise-testable
language $L$ and a finite lan… show more

**2018-12-05**

1812.01921 | math.GN

The notion of a difference hierarchy, first introduced by Hausdorff, plays an
important role in many… show more

**2018-05-08**

1805.03125 | cs.FL

Motivated by the study of word problems of monoids, we explore two ways of
viewing binary relations … show more