Subtree Oracle Pushdown Automata for Ranked and Unranked Ordered Trees

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F11%3A00184200" target="_blank" >RIV/68407700:21240/11:00184200 - isvavai.cz</a>
Result on the web
<a href="http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?reload=true&punumber=6068195" target="_blank" >http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?reload=true&punumber=6068195</a>
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Subtree Oracle Pushdown Automata for Ranked and Unranked Ordered Trees
Original language description
Oracle modification of subtree pushdown automata for ranked and unranked ordered trees is presented. Subtree pushdown automata [1] represent a complete index of a tree for subtrees. Subtree oracle pushdown automata, as inspired by string factor oracle automaton [2], have the number of states equal to n + 1, where n is the length of a corresponding linear notation of the tree. This makes the space complexity very low. By analogy with the string factor oracle automaton the subtree oracle automata can alsoaccept some subtrees which are not present in the given subject tree. However, the number of such false positive matches is smaller than in the case of the string factor oracle automaton. The presented pushdown automata are input-driven and therefore they can be determinised.
Czech name
—
Czech description
—

Project
<a href="/en/project/GA201%2F09%2F0807" target="_blank" >GA201/09/0807: String and tree analysis and processing</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)