Paper Info
Title
Subtree matching by deterministic pushdown automata
Abstract
Subtree matching is an important problem in Com- puter Science on which a number of tasks, such as mechanical theorem proving, term-rewriting, symbolic computation and non- procedural 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 autom ata.
Year
DOI
Venue
2009
10.1109/IMCSIT.2009.5352769
IMCSIT
Keywords
Field
DocType
automata,data mining,tree data structures,programming language,theorem proving,automata theory,prefix notation,construction industry,pattern matching,symbolic computation,deterministic pushdown automata,computational modeling,computer science,string matching,pushdown automata
Deterministic context-free grammar,Embedded pushdown automaton,Context-free language,Nondeterministic finite automaton,Nested word,Computer science,Deterministic pushdown automaton,Deterministic context-free language,Algorithm,Theoretical computer science,Pushdown automaton
Conference
Citations 
PageRank 
References 
2
0.44
5
Authors
3
Name
Order
Citations
PageRank
Tomás Flouri1596.89
Borivoj Melichar27216.63
Jan Janousek3234.80