Subtree Matching by Deterministic Pushdown Automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F09%3A00159738" target="_blank" >RIV/68407700:21230/09:00159738 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21240/09:00159738

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Subtree Matching by Deterministic Pushdown Automata

Popis výsledku v původním jazyce

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 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 then it is 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.

Název v anglickém jazyce

Subtree Matching by Deterministic Pushdown Automata

Popis výsledku anglicky

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 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 then it is 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.

Druh

D - Stať ve sborníku

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

V - Vyzkumna aktivita podporovana z jinych verejnych zdroju

Rok uplatnění

2009

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ů

Název statě ve sborníku

Proceedings of International Multiconference on Computer Science and Information Technology

ISBN

978-83-60810-22-4

ISSN

1896-7094

e-ISSN

—

Počet stran výsledku

8

Strana od-do

—

Název nakladatele

IEEE Computer Society Press

Místo vydání

New York

Místo konání akce

Mragowo

Datum konání akce

12. 10. 2009

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—