Subtree Oracle Pushdown Automata for Ranked and Unranked Ordered Trees

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

Subtree Oracle Pushdown Automata for Ranked and Unranked Ordered Trees

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Subtree Oracle Pushdown Automata for Ranked and Unranked Ordered Trees

Popis výsledku anglicky

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.

Druh

O - Ostatní výsledky

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F09%2F0807" target="_blank" >GA201/09/0807: Analýza a zpracování řetězců a stromů</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2011

Kód důvěrnosti údajů

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