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.fulltextWith Fulltext-
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.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

Google ScholarTM

Check

Altmetric


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