Termination Property of Inverse Finite Path Overlapping Term Rewriting System is Decidable
スポンサーリンク
概要
- 論文の詳細を見る
We propose a new decidable subclass of term rewriting systems (TRSs) for which strongly normalizing (SN) property is decidable. The new class is called almost orthogonal inverse finite path overlapping TRSs (AO-FPO^<-1>-TRSs) and the class properly includes AO growing TRSs for which SN is decidable. Tree automata technique is used to show that SN is decidable for AO-FPO^<-1>-TRSs.
- 社団法人電子情報通信学会の論文
- 2002-03-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
-
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