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

On the Size of Deterministic Finite Automata Obtained from XPath Expression

N/A
N/A
Protected

Academic year: 2021

シェア "On the Size of Deterministic Finite Automata Obtained from XPath Expression"

Copied!
1
0
0

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

全文

(1)IPSJ Transactions on Programming Vol.9 No.2 4 (May 2016). Abstract. On the Size of Deterministic Finite Automata Obtained from XPath Expression Akimasa Morihata1,a) Presented: November 5, 2015. XPath is fundamental to tree processing. It is well known that a core part of XPath, navigational top-down XPath, can be implemented by a top-down finite-state transition. However, to the author’s knowledge, it is not known how large the minimum deterministic finite automaton corresponding to an XPath expression can be. In this presentation, we show the following results. Given an XPath expression of size n, one can obtain a deterministic finite automaton of O(n) states if it does not contain predicates or descendant axes, whereas the number of states can be doubly-exponential to n otherwise. These results are not only theoretically interesting but also practically useful, especially for distributed XPath processing. They enable us to estimate sizes of messages exchanged between computation nodes. The results show that in the worst case, the message size should be exponential to the size of XPath expression, which indicates an inherent difficulty of distributed XPath processing.. 1 a). Graduate School of Arts and Sciences, The University of Tokyo, Meguro, Tokyo 153–8902, Japan [email protected]. c 2016 Information Processing Society of Japan . 4.

(2)

参照

関連したドキュメント

Keywords: continuous time random walk, Brownian motion, collision time, skew Young tableaux, tandem queue.. AMS 2000 Subject Classification: Primary:

The main problem upon which most of the geometric topology is based is that of classifying and comparing the various supplementary structures that can be imposed on a

Then it follows immediately from a suitable version of “Hensel’s Lemma” [cf., e.g., the argument of [4], Lemma 2.1] that S may be obtained, as the notation suggests, as the m A

Applications of msets in Logic Programming languages is found to over- come “computational inefficiency” inherent in otherwise situation, especially in solving a sweep of

Our method of proof can also be used to recover the rational homotopy of L K(2) S 0 as well as the chromatic splitting conjecture at primes p > 3 [16]; we only need to use the

Shi, “The essential norm of a composition operator on the Bloch space in polydiscs,” Chinese Journal of Contemporary Mathematics, vol. Chen, “Weighted composition operators from Fp,

A Darboux type problem for a model hyperbolic equation of the third order with multiple characteristics is considered in the case of two independent variables.. In the class

[2])) and will not be repeated here. As had been mentioned there, the only feasible way in which the problem of a system of charged particles and, in particular, of ionic solutions