Parallel Computation and Synchronized Term Rewriting Systems : Extended Abstract (Algebraic Semigroups, Formal Languages and Computation)
Ken-etsu Fujita, Aart Middeldorp · Kyoto University Research Information Repository (Kyoto University) · 2001
We present an extension of term rewriting systems with the mechanism of syn- chronization, called synchronized TRSs.The notion of synchronization is newly in- troduced for synchronizing applications of rewrite rules.The construction of $\mathrm{s}\mathrm{y}\mathrm{n}\mathrm{c}\mathrm{h}\mathrm{r}\triangleright$ nized TRSs can be regarded as acombination problem of TRSs.We prove fundamen- tal properties of synchronized ground TRSs:(1) Termination property is decidable for finite $\mathrm{r}\mathrm{i}\grave{\mathrm{g}}\mathrm{h}\mathrm{t}$ -ground synchronized TRSs.(2) The reachability problem for synchronized ground TRSs is undecidable.We show two prooS of the second result, using the halting problem for two counter automata and using Post's correspondence problem.The prooffi also reveal explic- itly arole of synchronization to be acorrespondence or coordination relation among computations.