Tree Automaton with Tree Memory
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we propose an extension of finite state tree automaton, called tree automaton with tree memory (TTA), and also define structure composing TTA (SC-TTA) and backward deterministic TTA (BD-TTA) as subclasses of TTA. We show that the classes of yield languages accepted by TTAs, SC-TTAs and BD-TTAs are equal to the class of recursively enumerable languages, the class of languages generated by tree-to-string finite state translation systems (TSFSTSs) and the class of languages generated by deterministic TSFSTSs, respectively. As a corollary, it is shown that the yield language accepted by an SC-TTA (resp. a BD-TTA) is linear space (resp. polynomial time) recognizable.
- 社団法人電子情報通信学会の論文
- 1998-02-25
著者
-
Nakanishi Ryuichi
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Seki Hiroyuki
Graduate School Of Information Science Nara Institute Of Science And Technology
-
HAYAKAWA Izumi
Optical Products Headquarters, Minolta Co., Ltd, Technical Center
-
Hayakawa Izumi
Optical Products Headquarters Minolta Co. Ltd Technical Center
関連論文
- Computational Complexity of Finding Meaningful Association Rules
- 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
- RNA Pseudoknotted Structure Prediction Using Stochastic Multiple Context-Free Grammar
- RIGHT-LINEAR FINITE PATH OVERLAPPING REWRITE SYSTEMS EFFECTIVELY PRESERVE RECOGNIZABILITY
- A Polynomial Time Learning Algorithm for Recognizable Series
- A Polynomial-Time Recognizable Subclass of Lexical-Functional Grammars
- A Note on Inadequacy of the Model for Learning from Queries
- A Labeled Transition Model A-LTS for History-Based Aspect Weaving and Its Expressive Power
- New certificate chain discovery methods for trust establishment in ad hoc networks and their evaluation (特集:次世代社会基盤をもたらす高度交通システムとモバイル通信システム)
- Policy Controlled System and Its Model Checking
- Decidability of the Security Verification Problem for Programs with Stack Inspection
- Tree Automaton with Tree Memory
- Static Analysis for k-secrecy against Inference Attacks
- An Efficient Method for Optimal Probe Deployment of Distributed IDS(Dependable Computing)
- RNA Pseudoknotted Structure Prediction Using Stochastic Multiple Context-Free Grammar
- Deciding Schema k-Secrecy for XML Databases
- A Static Analysis using Tree Automata for XML Access Control
- New Certificate Chain Discovery Methods for Trust Establishment in Ad Hoc Networks and Their Evaluation
- New Certificate Chain Discovery Methods for Trust Establishment in Ad Hoc Networks and Their Evaluation
- Runtime Control of a Program based on Quantitative Information Flow