Geodesic
Arbology: Trees and pushdown automata
Kybernetika, Tome 48 (2012) no. 3, pp. 402-428.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
Classification : 05C05, 68Q68
Keywords: trees; pushdown automata; tree pattern matching; indexing trees; arbology 
@article{KYB_2012__48_3_a4,
     author = {Melichar, Bo\v{r}ivoj and Janou\v{s}ek, Jan and Flouri, Tomas},
     title = {Arbology: {Trees} and pushdown automata},
     journal = {Kybernetika},
     pages = {402--428},
     publisher = {mathdoc},
     volume = {48},
     number = {3},
     year = {2012},
     mrnumber = {2975797},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2012__48_3_a4/}
}
TY  - JOUR
AU  - Melichar, Bořivoj
AU  - Janoušek, Jan
AU  - Flouri, Tomas
TI  - Arbology: Trees and pushdown automata
JO  - Kybernetika
PY  - 2012
SP  - 402
EP  - 428
VL  - 48
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2012__48_3_a4/
LA  - en
ID  - KYB_2012__48_3_a4
ER  - 
%0 Journal Article
%A Melichar, Bořivoj
%A Janoušek, Jan
%A Flouri, Tomas
%T Arbology: Trees and pushdown automata
%J Kybernetika
%D 2012
%P 402-428
%V 48
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2012__48_3_a4/
%G en
%F KYB_2012__48_3_a4
Melichar, Bořivoj; Janoušek, Jan; Flouri, Tomas. Arbology: Trees and pushdown automata. Kybernetika, Tome 48 (2012) no. 3, pp. 402-428. http://geodesic.mathdoc.fr/item/KYB_2012__48_3_a4/