ML p(r)ior | The omega-inequality problem for concatenation hierarchies of star-free languages

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.

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 2019-03-25 1903.10493 | math.GR This paper studies the classes of semigoups and monoids with context-free and deterministic context-… show more Highlights - Most important sentences from the article 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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2019-01-08
1901.02194 | cs.FL

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

Highlights - Most important sentences from the article

2017-12-22
1712.08455 | cs.FL

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2018-10-22
1810.09287 | cs.FL

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article