umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Tree pattern matching from regular tree expressions
Umeå University, Faculty of Science and Technology, Department of Computing Science. FASTAR Research Group, Stellenbosch University, South Africa. (Foundations of Language Processing)
2018 (English)In: Kybernetika (Praha), ISSN 0023-5954, E-ISSN 1805-949X, Vol. 54, no 2, p. 221-242Article in journal (Refereed) Published
Abstract [en]

In this work we deal with tree pattern matching over ranked trees, where the pattern set to be matched against is defined by a regular tree expression. We present a new method that uses a tree automaton constructed inductively from a regular tree expression. First we construct a special tree automaton for the regular tree expression of the pattern E, which is somehow a generalization of Thompson automaton for strings. Then we run the constructed automaton on the subject tree t. The pattern matching algorithm requires an O(vertical bar t vertical bar vertical bar E vertical bar) time complexity, where vertical bar t vertical bar is the number of nodes of t and vertical bar E vertical bar is the size of the regular tree expression E. The novelty of this contribution besides the low time complexity is that the set of patterns can be infinite, since we use regular tree expressions to represent patterns.

Place, publisher, year, edition, pages
Institute of Information Theory and Automation of The Czech Academy of Sciences , 2018. Vol. 54, no 2, p. 221-242
Keywords [en]
tree automata, Thompson Tree automata, regular tree expressions, tree pattern matching
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-151203DOI: 10.14736/kyb-2018-2-0221ISI: 000435168400001Scopus ID: 2-s2.0-85047410025OAI: oai:DiVA.org:umu-151203DiVA, id: diva2:1244908
Available from: 2018-09-03 Created: 2018-09-03 Last updated: 2018-09-03Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Cleophas, Loek

Search in DiVA

By author/editor
Cleophas, Loek
By organisation
Department of Computing Science
In the same journal
Kybernetika (Praha)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 292 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf