Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/20632
Full metadata record
DC FieldValueLanguage
dc.contributor.authorANTONOPOULOS, Timos-
dc.contributor.authorHOVLAND, Dag-
dc.contributor.authorMARTENS, Wim-
dc.contributor.authorNEVEN, Frank-
dc.date.accessioned2016-02-12T12:52:19Z-
dc.date.available2016-02-12T12:52:19Z-
dc.date.issued2015-
dc.identifier.citationTHEORY OF COMPUTING SYSTEMS, 57 (4), p. 967-1007-
dc.identifier.issn1432-4350-
dc.identifier.urihttp://hdl.handle.net/1942/20632-
dc.description.abstractNode 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.description.sponsorshipWe acknowledge the financial support of the Future and Emerging Technologies (FET) programme within the Seventh Framework Programme for Research of the European Commission, under the FET-Open grant agreement FOX, number FP7-ICT-233599. Supported by grant number MA 4938/2-1 from the Deutsche Forschungsgemeinschaft (Emmy Noether Nachwuchsgruppe).-
dc.language.isoen-
dc.publisherSPRINGER-
dc.rights© Springer Science+Business Media New York 2015-
dc.subject.otherAutomata; Twigs; Complexity; Definability-
dc.subject.otherautomata; twigs; complexity; definability-
dc.titleDeciding Twig-definability of Node Selecting Tree Automata-
dc.typeJournal Contribution-
dc.identifier.epage1007-
dc.identifier.issue4-
dc.identifier.spage967-
dc.identifier.volume57-
local.format.pages41-
local.bibliographicCitation.jcatA1-
dc.description.notes[Antonopoulos, Timos; Neven, Frank] Hasselt Univ, Hasselt, Belgium. [Antonopoulos, Timos; Neven, Frank] Transnat Univ Limburg, Hasselt, Belgium. [Hovland, Dag] Univ Oslo, Oslo, Norway. [Martens, Wim] Univ Bayreuth, Bayreuth, Germany.-
local.publisher.placeNEW YORK-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.identifier.doi10.1007/s00224-015-9623-7-
dc.identifier.isi000365792200006-
item.contributorANTONOPOULOS, Timos-
item.contributorHOVLAND, Dag-
item.contributorMARTENS, Wim-
item.contributorNEVEN, Frank-
item.fullcitationANTONOPOULOS, Timos; HOVLAND, Dag; MARTENS, Wim & NEVEN, Frank (2015) Deciding Twig-definability of Node Selecting Tree Automata. In: THEORY OF COMPUTING SYSTEMS, 57 (4), p. 967-1007.-
item.accessRightsRestricted Access-
item.fulltextWith Fulltext-
item.validationecoom 2016-
crisitem.journal.issn1432-4350-
crisitem.journal.eissn1433-0490-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
art%3A10.1007%2Fs00224-015-9623-7.pdf
  Restricted Access		Published version910.31 kBAdobe PDFView/Open    Request a copy
Show simple item record

SCOPUSTM   
Citations

1
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

1
checked on Apr 30, 2024

Page view(s)

84
checked on Sep 5, 2022

Download(s)

64
checked on Sep 5, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.