Membership and Reachability Problems for Row-Monomial Transformations

Abstract In this paper we study the membership and vector reachability problems for labelled transition systems with row-monomial transformations. We show the decidability of these problems for row-monomial martix semigroups over rationals and extend these results to the wider class of matrix semigroups. After that we apply our methods to reachability problems for a class of transition systems which turn out to be equivalent to specific counter machines.

Authors

• Alexei Lisitsa 0001
• Igor Potapov

Keywords

No keywords are indexed for this paper.