23 citations · 79 across the 26 of their papers we have counts for
6 papers · 1 filter
Covering and separation for logical fragments with modular predicates
Thomas Place, Varun Ramanathan, Pascal Weil
For every class of word languages, one may associate a decision problem called -separation. Given two regular languages, it asks whether there exists a t…
The FO^2 alternation hierarchy is decidable
Manfred Kufleitner, Pascal Weil
We consider the two-variable fragment FO^2[<] of first-order logic over finite words. Numerous characterizations of this class are known. Thérien and Wilke have shown that it is de…
On FO2 quantifier alternation over words
Manfred Kufleitner, Pascal Weil
We show that each level of the quantifier alternation hierarchy within FO^2[<] -- the 2-variable fragment of the first order logic of order on words -- is a variety of languages. W…
Algebraic recognizability of languages
Pascal Weil
Recognizable languages of finite words are part of every computer science cursus, and they are routinely described as a cornerstone for applications and for theory. We would like t…
The recognizability of sets of graphs is a robust property
Bruno Courcelle, Pascal Weil
Once the set of finite graphs is equipped with an algebra structure (arising from the definition of operations that generalize the concatenation of words), one can define the notio…
On the logical definability of certain graph and poset languages
Pascal Weil
We show that it is equivalent, for certain sets of finite graphs, to be definable in CMS (counting monadic second-order logic, a natural extension of monadic second-order logic), a…