Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426785 | Information and Computation | 2013 | 22 Pages |
Abstract
We characterize the importance of resources (like counters, channels, or alphabets) when measuring the expressiveness of Well-Structured Transition Systems (WSTS). We establish, for usual classes of well partial orders, the equivalence between the existence of order reflections (non-monotonic order embeddings) and the simulations with respect to coverability languages. We show that the non-existence of order reflections can be proved by the computation of order types. This allows us to extend the current classification of WSTS, in particular solving some open problems, and to unify the existing proofs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Rémi Bonnet, Alain Finkel, Serge Haddad, Fernando Rosa-Velardo,