About: Indexing ordered trees for (nonlinear) tree pattern matching

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Indexing ordered trees for (nonlinear) tree pattern matching Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://www.comsis.org/archive.php?show=vol0903
Description	A new kind of acyclic pushdown automata for an ordered tree is presented. The tree pattern pushdown automaton and the nonlinear tree pattern pushdown automaton represent a complete index of the tree for tree patterns and nonlinear tree patterns, respectively. Given a tree with n nodes, the numbers of distinct tree patterns and nonlinear tree patterns whichmatch the tree can be atmost 2n-1+n and at most (2+v)n-1+2, respectively, where v is the maximal number of nonlinear variables allowed in nonlinear tree patterns. The total sizes of nondeterministic versions of the two pushdown automata are O(n) and O(n2), respectively. We discuss the time complexities and show timings of our implementations using the bit-parallelismtechnique. The timings show that for a given tree the running time is linear to the size of the input pattern. The presented pushdown automata are input-driven and therefore can be also determinised. A new kind of acyclic pushdown automata for an ordered tree is presented. The tree pattern pushdown automaton and the nonlinear tree pattern pushdown automaton represent a complete index of the tree for tree patterns and nonlinear tree patterns, respectively. Given a tree with n nodes, the numbers of distinct tree patterns and nonlinear tree patterns whichmatch the tree can be atmost 2n-1+n and at most (2+v)n-1+2, respectively, where v is the maximal number of nonlinear variables allowed in nonlinear tree patterns. The total sizes of nondeterministic versions of the two pushdown automata are O(n) and O(n2), respectively. We discuss the time complexities and show timings of our implementations using the bit-parallelismtechnique. The timings show that for a given tree the running time is linear to the size of the input pattern. The presented pushdown automata are input-driven and therefore can be also determinised. (en)
Title	Indexing ordered trees for (nonlinear) tree pattern matching Indexing ordered trees for (nonlinear) tree pattern matching (en)
skos:prefLabel	Indexing ordered trees for (nonlinear) tree pattern matching Indexing ordered trees for (nonlinear) tree pattern matching (en)
skos:notation	RIV/68407700:21240/12:00196583!RIV13-MSM-21240___
http://linked.open...avai/predkladatel	Fakulta informačních technologií
http://linked.open...avai/riv/aktivita	S
http://linked.open...avai/riv/aktivity	S
http://linked.open...iv/cisloPeriodika	3
http://linked.open...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Melichar, Bořivoj Janoušek, Jan Trávníček, Jan
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	České vysoké učení technické v Praze / Fakulta informačních technologií
http://linked.open...dnocenehoVysledku	141148
http://linked.open...ai/riv/idVysledku	RIV/68407700:21240/12:00196583
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Tree patternmatching; nonlinear tree pattern matching; indexing (en)
http://linked.open.../riv/klicoveSlovo	nonlinear tree pattern matching indexing Tree patternmatching
http://linked.open...odStatuVydavatele	RS - Srbská republika
http://linked.open...ontrolniKodProRIV	[A6A7B7B69A9A]
http://linked.open...i/riv/nazevZdroje	COMSIS - Computer Science and Information Systems
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...UplatneniVysledku	2012
http://linked.open...v/svazekPeriodika	9
http://linked.open...iv/tvurceVysledku	Janoušek, Jan Melichar, Bořivoj Trávníček, Jan
http://linked.open...ain/vavai/riv/wos	000309649500007
issn	1820-0214
number of pages	29 (xsd:int)
http://bibframe.org/vocab/doi	10.2298/CSIS111220024T
http://localhost/t...ganizacniJednotka	21240
is http://linked.open...avai/riv/vysledek of	Indexing ordered trees for (nonlinear) tree pattern matching

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software