Layered Transducing Term Rewriting System and Its Recognizability Preserving Property (<Special Issue>Special Issue on Selected Papers from LA Symposium)
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 社団法人電子情報通信学会の論文
- 2003-02-01
著者
-
Kaji Y
Nara Inst. Of Sci. And Technol. Ikoma‐shi Jpn
-
Kaji Yuichi
Nara Inst. Of Sci. And Technol. Nara Jpn
-
Seki H
Graduate School Of Information Science Nara Institute Of Science And Technology
-
TAKAI Toshinori
National Institute of Advanced Industrial Science and Technology
-
SEKI Hiroyuki
Nara Institute of Science and Technology
-
FUJINAKA Youhei
Nara Institute of Science and Technology
-
Kaji Yuichi
Nara Inst. Of Sci. And Technol. Ikoma‐shi Jpn
-
Seki Hiroyuki
Nara Inst. Sci. And Technol. Ikoma‐shi Jpn
-
Takai Toshinori
Research Center For Verification And Semantics National Institute Of Advanced Industrial Science And
関連論文
- MAP and LogMAP Decoding Algorithms for Linear Block Codes Using a Code Structure(Special Section on Information Theory and Its Applications)
- Adaptive Recursive Maximum Likelihood Decoding Based on the Coarsest Parallel Concatenation Decomposition : Evaluation of the Decoding Complexity by Simulation
- A Time-Limited Key Management Scheme Based on a One-Way Permutation Tree
- A Formal Approach to Detecting Security Flaws in Object-Oriented Databases (Special Issue on New Generation Database Technologies)
- An Authorization Model for Object-Oriented Databases and Its Efficient Access Control
- Assignment of Data Types to Words in a Natural Language Specification
- Implementation of Natural Language Specifications of Communication Protocols by Executable Specifications
- A Translation Method from Natural Language Specifications of Communication Protocols into Algebraic Specifications Using Contextual Dependencies
- RNA Pseudoknotted Structure Prediction Using Stochastic Multiple Context-Free Grammar
- On the Generative Power of Grammars for RNA Secondary Structure(Foundations of Computer Science)
- RIGHT-LINEAR FINITE PATH OVERLAPPING REWRITE SYSTEMS EFFECTIVELY PRESERVE RECOGNIZABILITY
- Layered Transducing Term Rewriting System and Its Recognizability Preserving Property (Special Issue on Selected Papers from LA Symposium)
- Termination Property of Inverse Finite Path Overlapping Term Rewriting System is Decidable
- A Polynomial-Time Recognizable Subclass of Lexical-Functional Grammars
- A Note on Inadequacy of the Model for Learning from Queries
- Finite State Translation Systems and Parallel Multiple Context-Free Grammars
- The Universal Recognition Problems for Multiple Context-Free Grammars and for Linear Context-Free Rewriting Systems
- FOREWORD
- Using Loosely Triangular Form in Encoding LDPC codes with the LU-decomposition
- Policy Controlled System and Its Model Checking
- Decidability of the Security Verification Problem for Programs with Stack Inspection
- Formal Language Theoretic Approach to the Disclosure Tree Strategy in Trust Negotiation
- Comparison of the Expressive Power of Language-Based Access Control Models
- On the minimum weight of a certain subclass of array LDPC Codes
- FOREWORD
- A minimum weight test for a certain subclass of array LDPC codes(HISC2006)
- FEC-Based Reliable Transmission for Multiple Bursts in OBS Networks(Switching for Communications)
- Error Control for High-density Monochrome Two-dimensional Barcodes
- Encoding LDPC Codes Using the Triangular Factorization(Coding Theory,Information Theory and Its Applications)
- LTL Model Checking for Extended Pushdown Systems with Regular Tree Valuations