Layered Transducing Term Rewriting System and Its Recognizability Preserving Property

Toshinori TAKAI  Hiroyuki SEKI  Youhei FUJINAKA  Yuichi KAJI  

IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.2   pp.285-295
Publication Date: 2003/02/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: Term Rewriting Systems
term rewriting system,  tree automaton,  recognizability,  recognizability preserving property,  layered transducing TRS,  

Full Text: PDF(322.6KB)>>
Buy this Article

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 recognizability 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.