dc.date.accessioned |
2023-03-01T10:25:59Z |
|
dc.date.available |
2023-03-01T10:25:59Z |
|
dc.date.created |
2012-09-19T15:08:32Z |
|
dc.date.issued |
2012 |
|
dc.identifier.uri |
http://hdl.handle.net/123456789/3575 |
|
dc.description.abstract |
Node selecting tree automata (NSTAs) constitute a general formalism defining unary queries over trees. Basically, a node is selected by an NSTA when it is visited in a selecting state during an accepting run. We consider twig patterns as an abstraction of XPath. Since the queries definable by NSTAs form a strict superset of twig-definable queries, we study the complexity of the problem to decide whether the query by a given NSTA is twig-definable. In particular, we obtain that the latter problem is EXPTIME-complete. In addition, we show that it is also EXPTIME-complete to decide whether the query by a given NSTA is definable by a node selecting string automaton. |
|
dc.language |
EN |
|
dc.title |
Deciding Twig-definability of Node Selecting Tree Automata |
|
dc.type |
Academic chapter/article |
|
cristin.unitcode |
185,15,5,0 |
|
cristin.unitname |
Institutt for informatikk |
|
cristin.ispublished |
true |
|
dc.creator.author |
Antonopoulos, Timos |
|
dc.creator.author |
Hovland, Dag |
|
dc.creator.author |
Martens, Wim |
|
dc.creator.author |
Neven, Frank |
|
dc.identifier.cristin |
945066 |
|
dc.subject.nvi |
VDP::Databaser og multimediasystemer: 428VDP::Teoretisk databehandling, programmeringsspråk og -teori: 421 |
|
dc.type.document |
Kapittel |
|