Tree Indexing by Pushdown Automata and Repeats of Subtrees
Result description
We consider the problem of finding all subtree repeats in a given unranked ordered tree.We show a new, elegant, and simple method, which is based on the construction of a tree indexing structure called the subtree pushdown automaton. We propose a solution for computing all subtree repeats from the deterministic subtree pushdown automaton constructed over the subject tree. The method we present is directly analogous to the relationship between string deterministic suffix automata and factor repeats in agiven string.
Keywords
The result's identifiers
Result code in IS VaVaI
Result on the web
http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?reload=true&punumber=6068195
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Tree Indexing by Pushdown Automata and Repeats of Subtrees
Original language description
We consider the problem of finding all subtree repeats in a given unranked ordered tree.We show a new, elegant, and simple method, which is based on the construction of a tree indexing structure called the subtree pushdown automaton. We propose a solution for computing all subtree repeats from the deterministic subtree pushdown automaton constructed over the subject tree. The method we present is directly analogous to the relationship between string deterministic suffix automata and factor repeats in agiven string.
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Basic information
Result type
O - Miscellaneous
CEP
IN - Informatics
Year of implementation
2011