|
naistar (NAIST Academic Repository) >
学術リポジトリ naistar / NAIST Academic Repository naistar >
学術雑誌論文 / Journal Article >
情報科学研究科 / Graduate School of Information Science >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10061/4976
|
| Title: | Layered transducing term rewriting system and its recognizability preserving property |
| Authors: | Takai, Toshinori
Seki, Hiroyuki
Fujinaka, Youhei
Kaji, Yuichi |
| Issue Date: | 1-Feb-2003 |
| Publisher: | Institute of Electronics, Information and Communication Engineers |
| Journal Title: | IEICE transactions on information and systems |
| Volume: | E86-D |
| Issue: | 2 |
| Start page: | 285 |
| End page: | 295 |
| Abstract: | A term rewriting system which effectively preserves recognizability (EPR-TRS) has good mathematical properties, In this paper, a new subclass of TRSs, layered transducing TRSs (LT-TRSs) is defined and its rccognizability preserving property is discussed. The class of LT-TRSs contains some EPR-TRSs, e.g., {f(x)-f(g(x))} which do not belong to any of the known decidable subclasses of EPR-TRSs. Bottom-up linear tree transducer, which is a well-known computation model in the tree language theory, is a special case of LT-TRS. We present a sufficient condition for an LT-TRS to be an EPR-TRS. Also reachability and joinability are shown to be decidable for LT-TRSs. |
| URI: | http://hdl.handle.net/10061/4976 |
| URL: | http://search.ieice.org |
| ISSN: | 0916-8532 |
| Rights: | Copyright (C)2003 IEICE |
| Text Version: | publisher |
| Appears in Collections: | 情報科学研究科 / Graduate School of Information Science
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|
