umu.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Tree pattern matching from regular tree expressions
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. FASTAR Research Group, Stellenbosch University, South Africa. (Foundations of Language Processing)
2018 (engelsk)Inngår i: Kybernetika (Praha), ISSN 0023-5954, E-ISSN 1805-949X, Vol. 54, nr 2, s. 221-242Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Institute of Information Theory and Automation of The Czech Academy of Sciences , 2018. Vol. 54, nr 2, s. 221-242
Emneord [en]
tree automata, Thompson Tree automata, regular tree expressions, tree pattern matching
HSV kategori
Identifikatorer
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
Tilgjengelig fra: 2018-09-03 Laget: 2018-09-03 Sist oppdatert: 2018-09-03bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Personposter BETA

Cleophas, Loek

Søk i DiVA

Av forfatter/redaktør
Cleophas, Loek
Av organisasjonen
I samme tidsskrift
Kybernetika (Praha)

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 417 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf