| Presentation | 2002/1/23 Decidability of root-needed strategy in priority term rewriting system Tsuyoshi SUZUKI, Masahiko SAKAI, Toshiki SAKABE, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A term rewriting system (PRS, for short) is a term rewriting system equipped with a priority order over its rules. PRS's can model functional programs of which semantics is sensitive to the order that rules of a functional program are listed, and hence can be used to analyse properties of functional programs. In this peper we show that for any PRS, the set of redexes and the set of head normal forms are accepted by a tree automaton, respectively. We next show that for a linear PRS such that any rule has no variable common to the both hand sides, the reachability is decidable. Finally, we prove that the root-needed strategy for PRS's is decidable as well as that for TRS's by Durand. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | root-stable form / call-by-need computation |
| Paper # | COMP2001-80 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2002/1/23(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Decidability of root-needed strategy in priority term rewriting system |
| Sub Title (in English) | |
| Keyword(1) | root-stable form |
| Keyword(2) | call-by-need computation |
| 1st Author's Name | Tsuyoshi SUZUKI |
| 1st Author's Affiliation | Graduate School of Engineering, Nagoya University() |
| 2nd Author's Name | Masahiko SAKAI |
| 2nd Author's Affiliation | Graduate School of Engineering, Nagoya University |
| 3rd Author's Name | Toshiki SAKABE |
| 3rd Author's Affiliation | Graduate School of Engineering, Nagoya University |
| Date | 2002/1/23 |
| Paper # | COMP2001-80 |
| Volume (vol) | vol.101 |
| Number (no) | 630 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |