Détails sur le séminaire

Grande Salle de VERIMAG

14 janvier 2010 - 14h00
Reversal-bounded counter machines revisited
par Arnaud Sangnier de Universite de Turin

Abstract: We extend the class of reversal-bounded counter machines by authorizing a finite number of alternations between increasing and decreasing mode over a given bound. We prove that extended reversal-bounded counter machines also have effective semi-linear reachability sets and enjoy the same properties as the original reversal-bounded counter machines. We also prove that the property of being reversal-bounded is undecidable in general even when we fix the bound, whereas this problem becomes decidable when considering Vector Addition System with States.

This is a joint work with Alain Finkel.

Contact | Plan du site | Site réalisé avec SPIP 4.2.8 + AHUNTSIC [CC License]

info visites 3949242