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
AbstractLet A be a finite alphabet and A∗ the free monoid generated by A. A language is any subset o...
The quotient complexity, also known as state complexity, of a regular language is the number of dist...
This paper studies the fine structure of the Straubing hierarchy of star-free languages. Sequences o...
special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Appli...
International audienceWe survey recent results on the topological complexity of context-free omega-l...
New connections are discovered between formal language theory and model theory. We give logical char...
AbstractThis paper is a study of topological properties of omega context-free languages (ω-CFL). We ...
Abstract. In the seventies, several classification schemes for the rational languages were proposed,...
To appear in the Proceedings of the 16th EACSL Annual Conference on Computer Science and Logic, CSL ...
This paper is a study of topological properties of omega context free languages (ω-CFL). We first ex...
AbstractThis paper is a continuation of the study of topological properties of omega context free la...
We present a certain family of languages and show that for those languages infinite hierarchy of sta...
The main result of this paper is that the length of the Wadge hierarchy of omega context free langua...
It is proved that if definability of regular languages in the Sigma(n) fragment of the first-order l...
© Springer International Publishing Switzerland 2016. Over finitewords, there is a tight connection ...
AbstractLet A be a finite alphabet and A∗ the free monoid generated by A. A language is any subset o...
The quotient complexity, also known as state complexity, of a regular language is the number of dist...
This paper studies the fine structure of the Straubing hierarchy of star-free languages. Sequences o...
special issue dedicated to the second edition of the conference AutoMathA: from Mathematics to Appli...
International audienceWe survey recent results on the topological complexity of context-free omega-l...
New connections are discovered between formal language theory and model theory. We give logical char...
AbstractThis paper is a study of topological properties of omega context-free languages (ω-CFL). We ...
Abstract. In the seventies, several classification schemes for the rational languages were proposed,...
To appear in the Proceedings of the 16th EACSL Annual Conference on Computer Science and Logic, CSL ...
This paper is a study of topological properties of omega context free languages (ω-CFL). We first ex...
AbstractThis paper is a continuation of the study of topological properties of omega context free la...
We present a certain family of languages and show that for those languages infinite hierarchy of sta...
The main result of this paper is that the length of the Wadge hierarchy of omega context free langua...
It is proved that if definability of regular languages in the Sigma(n) fragment of the first-order l...
© Springer International Publishing Switzerland 2016. Over finitewords, there is a tight connection ...
AbstractLet A be a finite alphabet and A∗ the free monoid generated by A. A language is any subset o...
The quotient complexity, also known as state complexity, of a regular language is the number of dist...
This paper studies the fine structure of the Straubing hierarchy of star-free languages. Sequences o...
DOI
Add to ORKG