A Trichotomy for Regular Trail Queries

DOI10.46298/lmcs-19(4:20)2023arXiv1903.00226OpenAlexW2918223026MaRDI QIDQ6178699

Wim Martens, Unnamed Author, Matthias Niewerth

Publication date: 16 January 2024

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1903.00226

zbMATH Keywords

complexityquery languagesregular languagesdatabasesgraph databasestrailspath queriessimple paths

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• The method of forced enumeration for nondeterministic automata
• The directed subgraph homeomorphism problem
• The subgraph homeomorphism problem
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• Using forward reachability analysis for verification of lossy channel systems
• A trichotomy for regular simple path queries on graphs
• Dot-depth of star-free events
• The complexity of regular expressions and property paths in SPARQL
• The even-path problem for graphs and digraphs
• Nondeterministic Space is Closed under Complementation
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Modularity of cycles and paths in graphs
• Some results onC-varieties
• The Dot-Depth Hierarchy, 45 Years Later
• THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS
• Finding Regular Simple Paths in Graph Databases
• On finite monoids having only trivial subgroups
• On free monoids partially ordered by embedding
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Regular Expressions with Counting: Weak versus Strong Determinism

This page was built for publication: A Trichotomy for Regular Trail Queries