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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2019-05-24

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

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
PDF

Highlights - Most important sentences from the article

2015-11-05

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

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
PDF

Highlights - Most important sentences from the article

2018-04-24

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

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
PDF

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
PDF

Highlights - Most important sentences from the article

2018-03-21

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

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
PDF

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
PDF

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
PDF

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
PDF

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
PDF

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
PDF

Highlights - Most important sentences from the article

2018-12-05

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

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
PDF

Highlights - Most important sentences from the article