Arbology: trees and pushdown automata

Title:

Arbology: trees and pushdown automata

Creator:

Melichar, Bořivoj, Janoušek, Jan, and Flouri, Tomáš

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:01d9fbe8-015a-4f75-ad70-4a47d1fd3c66
uuid:01d9fbe8-015a-4f75-ad70-4a47d1fd3c66

Subject:

trees, pushdown automata, tree pattern matching, indexing trees, and arbology

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

[402]-428

Source:

Kybernetika | 2012 Volume:48 | Number:3

Harvested from:

CDK

Metadata only:

false