文献

J-GLOBAL ID：201802267148943568   整理番号：18A0935920

位置切断戦略を用いたプレフィックス制約付き線形単項書き換えのための認識可能なツリー言語の子孫【JST・京大機械翻訳】

Descendants of a recognizable tree language for prefix constrained linear monadic term rewriting with position cutting strategy

著者 (1件)： Vagvolgyi Sandor (Department of Foundations of Computer Science, University of Szeged, Arpad ter 2, H-6720 Szeged, Hungary)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 732  ページ： 60-72  発行年： 2018年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 木言語Lに対しては,正則σ経路言語の有限集合Z,およびΣ上のZプレフィックス制約線形一項項書換え規則の集合S,Sに対するLの位置切断は,位置切断戦略によるSの書き込みによりLの木から到達可能な木の集合S↑*(L)である。Lが認識できれば,S↑*(L)も認識可能である。さらに,Sが有限であれば,S↑*(L)を認識するツリーオートマトンを構築することができる。規則的なσ経路言語の認識可能な木言語Lと有限集合Zに対して,Σ上のZプレフィックス制約付き線形一項書換え規則のすべての集合に対して,Lの位置切削子孫の集合DZ,↑(L)を研究した。著者らは,DZ,↑(L)が有限であることを示して,LがツリーオートマトンAによって与えられるならば,Zの各要素がオートマトンによって与えられるならば,Z-プレフィックス制約線形単一項書換えシステムのセット{R1,...,Rk}を構築することができる。例えば,DZ,↑(L)={R*1↑(L),R*k↑(L)}。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 項書換え系 ,  *言語 ,  オートマトン ,  書換え規則 ,  *線形性 ,  木オートマトン ,  切削

著者キーワード (4件)： 単項項書き換えシステム ,  木オートマトン ,  木言語の子孫 ,  プレフィックス制約付き位置切断書換え戦略

分類 (1件)： オートマトン理論  (JB04000O)

タイトルに関連する用語 (6件)： 戦略 ,  プレフィックス ,  制約 ,  線形 ,  書き換え ,  言語