| dc.date.accessioned | 2016-01-08T14:23:26Z | |
| dc.date.available | 2016-04-17T22:30:55Z | |
| dc.date.created | 2015-06-19T10:59:06Z | |
| dc.date.issued | 2015 | |
| dc.identifier.citation | Antonopoulos, Timos Hovland, Dag Martens, Wim Neven, Frank . Deciding Twig-definability of Node Selecting Tree Automata. Theory of Computing Systems. 2015 | |
| dc.identifier.uri | http://hdl.handle.net/10852/48502 | |
| 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.
The final publication is available at Springer via http://dx.doi.org/10.1007/s00224-015-9623-7 | en_US |
| dc.language | EN | |
| dc.language.iso | en | en_US |
| dc.publisher | Springer-Verlag New York | |
| dc.title | Deciding Twig-definability of Node Selecting Tree Automata | en_US |
| dc.type | Journal article | en_US |
| dc.creator.author | Antonopoulos, Timos | |
| dc.creator.author | Hovland, Dag | |
| dc.creator.author | Martens, Wim | |
| dc.creator.author | Neven, Frank | |
| cristin.unitcode | 185,15,5,0 | |
| cristin.unitname | Institutt for informatikk | |
| cristin.ispublished | true | |
| cristin.fulltext | postprint | |
| cristin.qualitycode | 1 | |
| dc.identifier.cristin | 1249385 | |
| dc.identifier.bibliographiccitation | info:ofi/fmt:kev:mtx:ctx&ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Theory of Computing Systems&rft.volume=&rft.spage=&rft.date=2015 | |
| dc.identifier.jtitle | Theory of Computing Systems | |
| dc.identifier.volume | 57 | |
| dc.identifier.issue | 4 | |
| dc.identifier.startpage | 967 | |
| dc.identifier.endpage | 1007 | |
| dc.identifier.pagecount | 41 | |
| dc.identifier.doi | http://dx.doi.org/10.1007/s00224-015-9623-7 | |
| dc.identifier.urn | URN:NBN:no-52391 | |
| dc.type.document | Tidsskriftartikkel | en_US |
| dc.type.peerreviewed | Peer reviewed | |
| dc.source.issn | 1432-4350 | |
| dc.identifier.fulltext | Fulltext https://www.duo.uio.no/bitstream/handle/10852/48502/1/main.pdf | |
| dc.type.version | AcceptedVersion | |