Geodesic
Subtree Matching by Pushdown Automata
Computer Science and Information Systems, Tome 7 (2010) no. 2.

Voir la notice de l'article provenant de la source Computer Science and Information Systems website

Subtree matching is an important problem in Computer Science on which a number of tasks, such as mechanical theorem proving, term-rewriting, symbolic computation and nonprocedural programming languages are based on. A systematic approach to the construction of subtree pattern matchers by deterministic pushdown automata, which read subject trees in prefix and postfix notation, is presented. The method is analogous to the construction of string pattern matchers: for a given pattern, a nondeterministic pushdown automaton is created and is then determinised. In addition, it is shown that the size of the resulting deterministic pushdown automata directly corresponds to the size of the existing string pattern matchers based on finite automata.
Keywords: subtree, subtree matching, pushdown automata 
@article{CSIS_2010_7_2_a7,
     author = {Tomas Flouri and Jan Janousek and Borivoj Melichar},
     title = {Subtree {Matching} by {Pushdown} {Automata}},
     journal = {Computer Science and Information Systems},
     publisher = {mathdoc},
     volume = {7},
     number = {2},
     year = {2010},
     url = {http://geodesic.mathdoc.fr/item/CSIS_2010_7_2_a7/}
}
TY  - JOUR
AU  - Tomas Flouri
AU  - Jan Janousek
AU  - Borivoj Melichar
TI  - Subtree Matching by Pushdown Automata
JO  - Computer Science and Information Systems
PY  - 2010
VL  - 7
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CSIS_2010_7_2_a7/
ID  - CSIS_2010_7_2_a7
ER  - 
%0 Journal Article
%A Tomas Flouri
%A Jan Janousek
%A Borivoj Melichar
%T Subtree Matching by Pushdown Automata
%J Computer Science and Information Systems
%D 2010
%V 7
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CSIS_2010_7_2_a7/
%F CSIS_2010_7_2_a7
Tomas Flouri; Jan Janousek; Borivoj Melichar. Subtree Matching by Pushdown Automata. Computer Science and Information Systems, Tome 7 (2010) no. 2. http://geodesic.mathdoc.fr/item/CSIS_2010_7_2_a7/