DECIDABILITY OF REACHABILITY FOR DISJOINT UNION OF TERM REWRITING-SYSTEMS

Authors
CARON AC COQUIDE JL
Citation
Ac. Caron et Jl. Coquide, DECIDABILITY OF REACHABILITY FOR DISJOINT UNION OF TERM REWRITING-SYSTEMS, Theoretical computer science, 126(1), 1994, pp. 31-52
Citations number
21
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
126
Issue
1
Year of publication
1994
Pages
31 - 52
Database
ISI
SICI code
0304-3975(1994)126:1<31:DORFDU>2.0.ZU;2-L
Abstract
The reachability problem for term rewriting systems is the problem of deciding for a system S and two terms t and t', whether t can be reduc ed to t' with rules of S. On the one hand, we study the disjoint union of term rewriting systems the reachability problem of which is decida ble and give sufficient conditions for obtaining the modularity of dec idability of this problem. On the other hand, we study composition of constructor systems. This notion of composition does not imply disjoin tness.