Advanced Search
Japanese | English

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:

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.
ISSN: 0916-8532
Rights: Copyright (C)2003 IEICE
Text Version: publisher
Appears in Collections:情報科学研究科 / Graduate School of Information Science

Files in This Item:

File Description SizeFormat
IEICEI_e86-d_2_285.pdf325.11 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Copyright (c) 2007-2012 Nara Institute of Science and Technology All Rights Reserved.
DSpace Software Copyright © 2002-2010  Duraspace - Feedback