2009年
Compact Representation for Answer Sets of n-ary Regular Queries
IMPLEMENTATION AND APPLICATION OF AUTOMATA, PROCEEDINGS
- ,
- 巻
- 5642
- 号
- 開始ページ
- 94
- 終了ページ
- 104
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
An n-ary query over trees takes an input tree t and returns a set of n-tuples of the nodes of t. In this paper, a compact data structure is introduced for representing the answer sets of n-ary queries defined by tree automata. Despite that the number of the elements of the answer set can be as large as vertical bar t vertical bar(n), our representation allows to store the set using only O(3(n)vertical bar t vertical bar) space. Several basic operations on the sets are shown to be efficiently executable on the representation.
- リンク情報
- ID情報
-
- ISSN : 0302-9743
- Web of Science ID : WOS:000268667400010