32 citations · 35 across the 5 of their papers we have counts for
7 papers
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…
Infinitary Noetherian Constructions II. Transfinite Words and the Regular Subword Topology
Jean Goubault-Larrecq, Simon Halfon, Aliaume Lopez
We show that the spaces of transfinite words, namely ordinal-indexed words, over a Noetherian space, is also Noetherian, under a natural topology which we call the regular subword…
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…
On shuffle products, acyclic automata and piecewise-testable languages
Simon Halfon, Philippe Schnoebelen
We show that the shuffle $L \unicode{x29E2} F$ of a piecewise-testable language and a finite language is piecewise-testable. The proof relies on a classic but little-used a…
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…
Context-Free Commutative Grammars with Integer Counters and Resets
Dmitry Chistikov, Christoph Haase, Simon Halfon
We study the computational complexity of reachability, coverability and inclusion for extensions of context-free commutative grammars with integer counters and reset operations on…
Integer Vector Addition Systems with States
Christoph Haase, Simon Halfon
This paper studies reachability, coverability and inclusion problems for Integer Vector Addition Systems with States (ZVASS) and extensions and restrictions thereof. A ZVASS compri…