##
###
Reachability in Unions of Commutative Rewriting Systems Is Decidable
[chapter]

Mikołaj Bojańczyk, Piotr Hoffman

*
STACS 2007
*

We consider commutative string rewriting systems (Vector Addition Systems, Petri nets), i.e., string rewriting systems in which all pairs of letters commute. We are interested in reachability: given a rewriting system R and words v and w, can v be rewritten to w by applying rules from R? A famous result states that reachability is decidable for commutative string rewriting systems. We show that reachability is decidable for a union of two such systems as well. We obtain, as a special case, that
## more »

... special case, that if h : U → S and g : U → T are homomorphisms of commutative monoids, then their pushout has a decidable word problem. Finally, we show that, given commutative monoids U , S and T satisfying S ∩ T = U , it is decidable whether there exists a monoid M such that S ∪ T ⊆ M ; we also show that the problem remains decidable if we require M to be commutative, too. Topic classification: Logic in computer science -rewriting 1 Summary of results A string rewriting system R over a finite alphabet Σ is simply a finite set of rules of the form v → w, where v and w are words over Σ (string rewriting systems are also called semi-Thue systems). Such a system defines a one-step rewriting relation → R and a multistep rewriting relation → * R on words over Σ: a word v rewrites in one step to a word w if there exist words t, v 0 , u, w 0 ∈ Σ * such that v = tv 0 u, w = tw 0 u and v 0 → w 0 is a rule of R; the multistep rewriting relation is the reflexive-transitive closure of the one-step relation. In the sequel, the statement "v rewrites to w in R" shall mean that v → * R w. The (uniform) reachability problem is defined as follows: Given a string rewriting system R and words v and w in the alphabet of that system, answer whether v rewrites to w in R? This problem is one of the most basic undecidable problems. However, for appropriate restrictions on the form of the rewriting system R, the problem may become decidable. A string rewriting system is said to be commutative if for any two letters a and b of the alphabet it contains the rule ab → ba. Commutative string rewriting systems are also called Vector Addition Systems or Multiset Rewriting Systems, since they treat words as multisets of letters -or elements of N Σ , where Σ is the alphabet. These systems are equivalent to Petri nets. The following is a famous result [1, 2]:

doi:10.1007/978-3-540-70918-3_53
dblp:conf/stacs/BojanczykH07
fatcat:uwao3tvwjbhbvjywjgmn3ufjzi