文章基本信息

标题：Pattern Matching of Incompletely RE-Typed Expressions via Transformation
本地全文：下载
作者：Satoshi Okui ; Taro Suzuki
期刊名称：Information and Media Technologies
电子版ISSN：1881-0896
出版年度：2006
卷号：1
期号：2
页码：819-832
DOI：10.11185/imt.1.819
出版社：Information and Media Technologies Editorial Board
摘要：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.