Deciding Twig-definability of Node Selecting Tree Automata

dc.date.accessioned	2023-02-20T22:47:35Z
dc.date.available	2023-02-20T22:47:35Z
dc.date.created	2012-09-19T15:08:32Z
dc.date.issued	2012
dc.identifier.uri	http://hdl.handle.net/123456789/320
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.
dc.language	EN
dc.title	Deciding Twig-definability of Node Selecting Tree Automata
dc.type	Academic chapter/article
cristin.unitcode	185,15,5,0
cristin.unitname	Institutt for informatikk
cristin.ispublished	true
dc.creator.author	Antonopoulos, Timos
dc.creator.author	Hovland, Dag
dc.creator.author	Martens, Wim
dc.creator.author	Neven, Frank
dc.identifier.cristin	945066
dc.subject.nvi	VDP::Databaser og multimediasystemer: 428VDP::Teoretisk databehandling, programmeringsspråk og -teori: 421
dc.type.document	Kapittel