Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13962
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | ANTONOPOULOS, Timos | - |
dc.contributor.author | HOVLAND, Dag | - |
dc.contributor.author | MARTENS, Wim | - |
dc.contributor.author | NEVEN, Frank | - |
dc.date.accessioned | 2012-09-06T14:15:17Z | - |
dc.date.available | 2012-09-06T14:15:17Z | - |
dc.date.issued | 2012 | - |
dc.identifier.citation | Deutsch, Alin (Ed.). Proceedings of the 15th International Conference on Database Theory, p. 61-73 | - |
dc.identifier.isbn | 978-1-4503-0791-8 | - |
dc.identifier.uri | http://hdl.handle.net/1942/13962 | - |
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 de- cide whether the query by a given NSTA is definable by a node selecting string automaton. | - |
dc.language.iso | en | - |
dc.publisher | ACM | - |
dc.rights | Copyright 2012 ACM 978-1-4503-0791-8/12/03 | - |
dc.subject.other | automata; twigs; complexity; definability | - |
dc.title | Deciding twig-definability of node selecting tree automata | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.authors | Deutsch, Alin | - |
local.bibliographicCitation.conferencedate | 26-29 March 2012 | - |
local.bibliographicCitation.conferencename | 15th International Conference on Database Theory (ICDT 2012) | - |
local.bibliographicCitation.conferenceplace | Berlin, Germany | - |
dc.identifier.epage | 73 | - |
dc.identifier.spage | 61 | - |
local.bibliographicCitation.jcat | C1 | - |
local.publisher.place | New York, NY, USA | - |
local.type.refereed | Refereed | - |
local.type.specified | Proceedings Paper | - |
dc.bibliographicCitation.oldjcat | C3 | - |
local.relation.fp7 | 233599 | - |
dc.identifier.doi | 10.1145/2274576.2274584 | - |
dc.identifier.url | http://dl.acm.org/citation.cfm?doid=2274576.2274584 | - |
local.bibliographicCitation.btitle | Proceedings of the 15th International Conference on Database Theory | - |
item.contributor | ANTONOPOULOS, Timos | - |
item.contributor | HOVLAND, Dag | - |
item.contributor | MARTENS, Wim | - |
item.contributor | NEVEN, Frank | - |
item.accessRights | Open Access | - |
item.fullcitation | ANTONOPOULOS, 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.fulltext | With Fulltext | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
p61-antonopoulos.pdf | 485.54 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.