The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings

Autor: Philippe Schnoebelen, K. Narayan Kumar, Simon Halfon, Prateek Karandikar, Jean Goubault-Larrecq

Publikováno v: Well Quasi-Orders in Computation, Logic, Language and Reasoning
Well Quasi-Orders in Computation, Logic, Language and Reasoning, 53, Springer, pp.55-105, 2020, Trends in Logic, 978-3-030-30228-3. ⟨10.1007/978-3-030-30229-0_3⟩
Trends in Logic ISBN: 9783030302283

International audience; 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 sets. These algorithms can be built in a generic

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3f3179025119cf969bf1651af4a97c7c
https://hal.archives-ouvertes.fr/hal-03083290

Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering

Autor: 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 $\Sigma_1$ theory is undecidable (already over two letters). We investigate the decidability border by c

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d1aad3bb73fbe779d768ac13744e762f

Integer Vector Addition Systems with States

Autor: Christoph Haase, Simon Halfon

Publikováno v: Lecture Notes in Computer Science ISBN: 9783319114385

This paper studies reachability, coverability and inclusion problems for Integer Vector Addition Systems with States (ZVASS) and extensions and restrictions thereof. A ZVASS comprises a finite-state controller with a finite number of counters ranging

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::35726cd876bf46fc4d940ecaaf7f15f3
https://doi.org/10.1007/978-3-319-11439-2_9