32 citations · 35 across the 5 of their papers we have counts for
3 papers · 1 filter
Measuring well quasi-ordered finitary powersets
Sergio Abriola, Simon Halfon, Aliaume Lopez +3
The complexity of a well-quasi-order (wqo) can be measured through three ordinal invariants: the width as a measure of antichains, height as a measure of chains, and maximal order…
The Ideal Approach to Computing Closed Subsets in Well-Quasi-Ordering
Jean Goubault-Larrecq, Simon Halfon, Prateek Karandikar +2
Elegant and general algorithms for handling upwards-closed and downwards-closed subsets of WQOs can be developed using the filter-based and ideal-based representation for these set…
Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering
Simon Halfon, Philippe Schnoebelen, Georg Zetzsche
We consider first-order logic over the subword ordering on finite words, where each word is available as a constant. Our first result is that the theory is undecidable (alrea…