Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/13962
Full metadata record
DC FieldValueLanguage
dc.contributor.authorANTONOPOULOS, Timos-
dc.contributor.authorHOVLAND, Dag-
dc.contributor.authorMARTENS, Wim-
dc.contributor.authorNEVEN, Frank-
dc.date.accessioned2012-09-06T14:15:17Z-
dc.date.available2012-09-06T14:15:17Z-
dc.date.issued2012-
dc.identifier.citationDeutsch, Alin (Ed.). Proceedings of the 15th International Conference on Database Theory, p. 61-73-
dc.identifier.isbn978-1-4503-0791-8-
dc.identifier.urihttp://hdl.handle.net/1942/13962-
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 de- cide whether the query by a given NSTA is definable by a node selecting string automaton.-
dc.language.isoen-
dc.publisherACM-
dc.rightsCopyright 2012 ACM 978-1-4503-0791-8/12/03-
dc.subject.otherautomata; twigs; complexity; definability-
dc.titleDeciding twig-definability of node selecting tree automata-
dc.typeProceedings Paper-
local.bibliographicCitation.authorsDeutsch, Alin-
local.bibliographicCitation.conferencedate26-29 March 2012-
local.bibliographicCitation.conferencename15th International Conference on Database Theory (ICDT 2012)-
local.bibliographicCitation.conferenceplaceBerlin, Germany-
dc.identifier.epage73-
dc.identifier.spage61-
local.bibliographicCitation.jcatC1-
local.publisher.placeNew York, NY, USA-
local.type.refereedRefereed-
local.type.specifiedProceedings Paper-
dc.bibliographicCitation.oldjcatC3-
local.relation.fp7233599-
dc.identifier.doi10.1145/2274576.2274584-
dc.identifier.urlhttp://dl.acm.org/citation.cfm?doid=2274576.2274584-
local.bibliographicCitation.btitleProceedings of the 15th International Conference on Database Theory-
item.contributorANTONOPOULOS, Timos-
item.contributorHOVLAND, Dag-
item.contributorMARTENS, Wim-
item.contributorNEVEN, Frank-
item.accessRightsOpen Access-
item.fullcitationANTONOPOULOS, Timos; HOVLAND, Dag; MARTENS, Wim & NEVEN, Frank (2012) Deciding twig-definability of node selecting tree automata. In: Deutsch, Alin (Ed.). Proceedings of the 15th International Conference on Database Theory, p. 61-73.-
item.fulltextWith Fulltext-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
p61-antonopoulos.pdf485.54 kBAdobe PDFView/Open
Show simple item record

Google ScholarTM

Check

Altmetric


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