We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Containment of UC2RPQ: The Hard and Easy Cases

00:00
Untertitel
Aus
Abspielgeschwindigkeit
1
Untertitel
Aus
Englisch (automatisch erzeugt)
Abspielgeschwindigkeit
0.25
0.5
0.75
1
1.25
1.5
1.75
2
Qualität
576p
19
 Zitieren
 Teilen
 Zugehöriges Material
 Herunterladen Bestellen
Kein Logo verfügbarInternational Conference on Database Theory (ICDT)
 Figueira, Diego

Formale Metadaten

Titel
Containment of UC2RPQ: The Hard and Easy Cases
Serientitel
Anzahl der Teile
25
Autor
Lizenz
CC-Namensnennung - keine Bearbeitung 3.0 Deutschland:
Sie dürfen das Werk in unveränderter Form zu jedem legalen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
We study the containment problem for UC2RPQ, that is, two-way Regular Path Queries, closed under conjunction, projection and union. We show a dichotomy property between PSpace-c and ExpSpace-c based on a property on the underlying graph of queries. We show that for any class C of graphs, the containment problem for queries whose underlying graph is in C is in PSpace if and only if C has bounded bridgewidth. Bridgewidth is a graph measure we introduce to this end, defined as the maximum size of a minimal edge separator of a graph.
00:00
Data Encryption StandardFinite-Elemente-MethodeRegulärer GraphVirtualisierungDatenbankMultigraphGraphAbfrageComputeranimation
00:18
RahmenproblemGraphFinitismusZeichenvorratDesign by ContractMaßerweiterungGebäude <Mathematik>Beobachtungsstudiep-BlockZellularer AutomatRegulärer GraphFormale SpracheComputeranimation
00:33
BildschirmmaskeRekursive FunktionMaßerweiterungGebäude <Mathematik>Graphp-BlockOrdinalzahlAbfrageComputeranimation
00:52
KnotenpunktRelativitätstheorieReguläre SpracheBildschirmmaskeComputeranimation
01:03
Regulärer GraphMultigraphReguläre SpracheSchnittmengeComputeranimation
01:13
ResultanteDivergente ReiheGraphVorzeichen <Mathematik>DatenbankComputeranimation
01:26
LeistungsbewertungGraphFormale SemantikAbfrageIRIS-TMultigraphGerichteter GraphComputeranimation
01:45
Elektronische PublikationGerichteter GraphBildschirmmaskeWort <Informatik>Folge <Mathematik>MultigraphFormale Sprache
02:03
Generator <Informatik>
02:26
Funktion <Mathematik>KnotenmengeSchnittmengeAbfrageTonnelierter RaumComputeranimation
02:55
ResultanteBeobachtungsstudieDatenbankGraphComputeranimation
03:23
Elektronische PublikationComputeranimation
03:38
SchlussregelFermatsche VermutungNP-hartes ProblemAbfrageVariableResultanteQuadratzahlComputeranimation
03:58
SchlussregelBoolesche AlgebraShape <Informatik>VollständigkeitSchnittmengeFormale SpracheAggregatzustandGraphfärbungComputeranimation
04:26
SchlussregelElektronische PublikationAbfrageSchnittmengeFormale SpracheXML
04:44
Elektronische PublikationZahlenbereichBildgebendes VerfahrenMultigraphAbfrageParallele SchnittstelleKategorie <Mathematik>Computeranimation
05:02
SchlussregelEinflussgrößeShape <Informatik>Klasse <Mathematik>EreignishorizontGRASS <Programm>AggregatzustandProgrammierungMinkowski-MetrikGraphfärbungPhysikalische TheorieBridge <Kommunikationstechnik>MagnettrommelspeicherEndliche ModelltheorieCliquenweiteVollständigkeitAbfrageTheoremComputeranimation
05:57
TheoremTopologieGraphProzess <Informatik>
06:17
Elektronische PublikationRahmenproblemBridge <Kommunikationstechnik>Luenberger-BeobachterVollständigkeit
06:34
Elektronische PublikationKlasse <Mathematik>EinflussgrößeMultigraphVollständigkeitCliquenweite
07:00
Bridge <Kommunikationstechnik>CliquenweiteEinflussgrößeElement <Gruppentheorie>Klasse <Mathematik>GraphWeb-SeiteGRASS <Programm>Computeranimation
07:32
Lie-GruppeMultigraphElektronische PublikationTopologieUmsetzung <Informatik>CliquenweiteBridge <Kommunikationstechnik>Klasse <Mathematik>StichprobenumfangCASE <Informatik>ErneuerungstheorieComputeranimation
08:08
SchlussregelHill-DifferentialgleichungGraphBridge <Kommunikationstechnik>Parallele SchnittstelleCliquenweite
08:20
SchlussregelZahlenbereichWhiteboardLokales MinimumGRASS <Programm>Bridge <Kommunikationstechnik>MultigraphCliquenweiteSchnittmengeGraphEinfach zusammenhängender RaumComputeranimation
08:43
Elektronische PublikationGradientGRASS <Programm>Shape <Informatik>ResultanteMultigraphMinkowski-MetrikKlasse <Mathematik>DichotomieComputeranimation
09:04
GradientElektronische PublikationSchlussregelMultigraphTopologieParallele SchnittstelleBridge <Kommunikationstechnik>InstantiierungZahlenbereichFamilie <Mathematik>CliquenweiteComputeranimation
09:18
SchlussregelPhysikalische TheorieInstantiierungResultanteAggregatzustandFolge <Mathematik>EinsMinkowski-MetrikInverseOrdnungsreduktionMultigraphBridge <Kommunikationstechnik>CliquenweiteHelmholtz-ZerlegungComputeranimation
10:07
Lokales MinimumIkosaederSchlussregelAbfrageTheoremInverseComputeranimation
10:35
SchlussregelE-FunktionTheoremComputeranimation
10:44
Elektronische PublikationGRASS <Programm>Prädiktor-Korrektor-VerfahrenProzess <Informatik>Formale SpracheKlasse <Mathematik>Web-SeiteTermRegulärer Ausdruck <Textverarbeitung>TabelleSchnittmengeShape <Informatik>Reguläre SpracheAbfrageComputeranimation
11:35
SchlussregelMachsches PrinzipWeb-SeiteRegulärer Ausdruck <Textverarbeitung>AbfrageBeobachtungsstudieMAPComputeranimation
12:10
VerschlingungComputeranimation
Transkript: Englisch(automatisch erzeugt)