| dc.date.accessioned | 2013-03-12T08:15:21Z | |
| dc.date.available | 2013-03-12T08:15:21Z | |
| dc.date.issued | 2012 | en_US |
| dc.date.submitted | 2012-09-26 | en_US |
| dc.identifier.uri | http://hdl.handle.net/10852/9113 | |
| 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.
Copyright ACM, 2012. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 15th International Conference on Database Theory. | eng |
| dc.language.iso | eng | en_US |
| dc.title | Deciding Twig-definability of Node Selecting Tree Automata | en_US |
| dc.type | Chapter | en_US |
| dc.date.updated | 2012-09-26 | en_US |
| dc.creator.author | Antonopoulos, Timos | en_US |
| dc.creator.author | Hovland, Dag | en_US |
| dc.creator.author | Martens, Wim | en_US |
| dc.creator.author | Neven, Frank | en_US |
| dc.subject.nsi | VDP::420 | en_US |
| dc.identifier.cristin | 945066 | en_US |
| dc.identifier.startpage | 61 | |
| dc.identifier.endpage | 73 | |
| dc.identifier.doi | 10.1145/2274576.2274584 | |
| dc.identifier.urn | URN:NBN:no-32389 | en_US |
| dc.type.document | Bokkapittel | en_US |
| dc.identifier.duo | 169424 | en_US |
| dc.type.peerreviewed | Peer reviewed | en_US |
| dc.identifier.fulltext | Fulltext https://www.duo.uio.no/bitstream/handle/10852/9113/1/institution_archive_copy.pdf | |
| dc.type.version | AcceptedVersion | |
| cristin.btitle | 15th International Conference on Database Theory, ICDT '12, Berlin, Germany, March 26-29, 2012 | |