Subtree matching by pushdown automata | Zendy

Tomáš Flouri | Zendy; Jan Janoušek | Zendy; Bořivoj Melichar | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Subtree matching by pushdown automata

Author(s) -

Tomáš Flouri,

Jan Janoušek,

Bořivoj Melichar

Publication year - 2010

Publication title -

computer science and information systems

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.244

H-Index - 24

eISSN - 2406-1018

pISSN - 1820-0214

DOI - 10.2298/csis1002331f

Subject(s) - deterministic pushdown automaton , pushdown automaton , computer science , embedded pushdown automaton , nondeterministic algorithm , string (physics) , rewriting , nested word , deterministic context free grammar , nondeterministic finite automaton , theoretical computer science , pattern matching , string searching algorithm , approximate string matching , automaton , programming language , automata theory , mathematics , quantum finite automata , parsing , context free grammar , tree adjoining grammar , mathematical physics

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 and postfix 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 is then 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research