ARBOLOGY: TREES AND PUSHDOWN AUTOMATA

作者：Melichar Borivoj^*; Janousek Jan; Flouri Tomas

来源：Kybernetika, 2012, 48(3): 402-428.

• trees
• pushdown automata
• tree pattern matching
• indexing trees
• arbology

We present a unified and systematic approach to basic principles of Arbology, a new algorithmic discipline focusing on algorithms on trees. Stringology, a highly developed algorithmic discipline in the area of string processing, can use finite automata as its basic model of computation. For various kinds of linear notations of ranked and unranked ordered trees it holds that subtrees of a tree in a linear notation are substrings of the tree in the linear notation. Arbology uses pushdown automata reading such linear notations of trees as its basic model of computation. Basic principles known from stringology are used for the construction of particular arbology algorithms, in which the underlying tree structure is processed with the use of the pushdown store. Arbology results are shown for the basic problems subtree matching and tree indexing for ranked and unranked ordered trees.

• 出版日期2012