Pattern Matching of Incompletely RE-Typed Expressions via Transformation

DOI

この論文をさがす

説明

We offer a pattern-matching algorithm based on incomplete regular expression (IRE, for short) types. IRE types extend the regular expression types introduced by Hosoya and Pierce in the programming language XDuce. Pattern-matching for IRE-typed expressions provides a capability to uniformly access “context” parts of XML document trees within the framework of pattern-matching theory; we do not rely on external facilities (or notations) such as XPath. In order to describe our pattern-matching algorithm, we adopt a rule-based approach; that is, we present our algorithm as a set of a few simple transformation rules. These rules simulate a transition in non-deterministic top-down tree automata(though we do not deal with tree automata explicitly), while also accumulating bindings for pattern variables. Our pattern-matching algorithm is sound and complete: it enumerates all correct but no incorrect solutions. We give rigorous proofs of these properties. A small but non-trivial example illustrates the expressiveness of our framework.

収録刊行物

詳細情報 詳細情報について

  • CRID
    1390001205265211008
  • NII論文ID
    130000058355
  • DOI
    10.11185/imt.1.819
  • ISSN
    18810896
  • 本文言語コード
    en
  • データソース種別
    • JaLC
    • CiNii Articles
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ