• 検索結果がありません。

木から文字列への決定性降下型変換器の早期化

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "木から文字列への決定性降下型変換器の早期化"

Copied!
1
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 1 ページ )

全文

(1)情報処理学会論文誌. プログラミング. Vol.12 No.2 13 (May 2019). 発表概要. 木から文字列への決定性降下型変換器の早期化 高橋 祐多1,a). 中野 圭介2,b). 2018年10月31日発表. 木から文字列への決定性降下型変換器（deterministic top-down tree-to-string transducers，yDTs）は， 木構造データを入力とし，文字列を出力するような関数を扱うモデルの 1 つである．与えられた 2 つの. yDT が，あらゆる同じ入力に対して同じ出力をするかという等価性判定は，決定可能であることが知ら れている．既存の等価性判定アルゴリズムは，2 つの半アルゴリズムを組み合わせることで等価性判定を 行っているため，計算量の見積りが不可能である．一方，yDT が線型の場合，正規形を求めることでたか だか指数時間で決定できることが知られている．そのアルゴリズムでは，言語の最大共通接頭辞・接尾辞 や周期性を利用することで早期化を行った後，最小化することで正規形を求め，等価性判定を行っている． そこで，計算量を見積もることができる yDT の等価性判定アルゴリズムの実現に向け，本発表では線型 yDT の等価性判定アルゴリズムにおいて用いられる早期化を非線型 yDT に対して適用できるよう一般化 する．具体的には，yDT に対して正規先読みを追加することで，早期に出力可能な文字列を可能な限り早 く出力する正規先読み付き yDT を構築する．. Presentation Abstract. Earliest form on Deterministic Top-down Tree-to-string Transducers Yuta Takahashi1,a). Keisuke Nakano2,b). Presented: October 31, 2018. A deterministic top-down tree-to-string transducer (yDT) is a model of functions which transform treestructured data to a string. It is known that the equivalence problem on yDTs is decidable, that is, we can effectively check if given two yDTs output the same string for every input. Since the existing algorithm for the equivalence problem consists of two semi-algorithms, it is impossible to estimate its computational complexity. In the case where given yDTs are linear, the equivalence can be decided in at most exponential time to the size of yDT through their ‘normal forms’ which is obtained by constructing earliest yDT and minimizing the size of it. This approach relies on properties of the longest common prefix/suffix and the periodicity of language, which has never been discussed for general yDTs. In this presentation, we study earliest yDTs as the first step of another algorithm of which computational complexity can be determined. We introduce regular-lookahead to yDTs for generalizing the construction of earliest linear yDT. It makes it possible that the rule of yDT yields string as possible as earlier.. This is the abstract of an unrefereed presentation, and it should not preclude subsequent publication. 1. 2. a) b). 電気通信大学大学院情報理工学研究科情報・ネットワーク工学専 攻 Graduate School of Informatics and Engineering, The University of Electro-Communications, Chofu, Tokyo 182–8585, Japan 東北大学電気通信研究所 Research Institute of Electrical Communication, Tohoku University, Sendai, Miyagi 980–8577, Japan [email protected] [email protected]. c 2019 Information Processing Society of Japan . 13.

(2)

参照

今ダウンロードする ( PDF - 1 ページ - 98.28 KB )

関連したドキュメント

The unique solvability of the problem is established

Kilbas; Conditions of the existence of a classical solution of a Cauchy type problem for the diffusion equation with the Riemann-Liouville partial derivative, Differential Equations,

This problem is a generalization of the well known Neumann problems

Turmetov; On solvability of a boundary value problem for a nonhomogeneous biharmonic equation with a boundary operator of a fractional order, Acta Mathematica Scientia.. Bjorstad;

A sufficient condition for the energy of a point such that a local minimum of the energy exists at every triangular lattice point is obtained

In [7], assuming the well- distributed points to be arranged as in a periodic sphere packing [10, pp.25], we have obtained the minimum energy condition in a one-dimensional case;

Cummins that every algebraic curvature tensor has a structure which is very similar to that of the above Osserman curvature tensors

For a positive definite fundamental tensor all known examples of Osserman algebraic curvature tensors have a typical structure.. They can be produced from a metric tensor and a

SIMPLICIAL APPROXIMATION

In that same language, we can show that every fibration which is a weak equivalence has the “local right lifting property” with respect to all inclusions of finite simplicial

If

We give another global upper bound for Jensen’s discrete inequal- ity which is better than already existing ones.. For instance, we determine a new converses for generalized A–G and

2. Formulation of the Problem

It is known that if the Dirichlet problem for the Laplace equation is considered in a 2D domain bounded by sufficiently smooth closed curves, and if the function specified in the

We prove that for some form of the nonlinear term these simple modes are stable provided that their energy is large enough

We prove that for some form of the nonlinear term these simple modes are stable provided that their energy is large enough.. Here stable means orbitally stable as solutions of