Search

Your search keyword '"Niehren, Joachim"' showing total 419 results
Start Over Author "Niehren, Joachim"
419 results on '"Niehren, Joachim"'

1. Linear Programs with Conjunctive Database Queries

Author

Capelli, Florent, Crosetti, Nicolas, Niehren, Joachim, and Ramon, Jan

Subjects
Computer Science - Databases
Abstract

In this paper, we study the problem of optimizing a linear program whose variables are the answers to a conjunctive query. For this we propose the language LP(CQ) for specifying linear programs whose constraints and objective functions depend on the answer sets of conjunctive queries. We contribute an efficient algorithm for solving programs in a fragment of LP(CQ). The natural approach constructs a linear program having as many variables as there are elements in the answer set of the queries. Our approach constructs a linear program having the same optimal value but fewer variables. This is done by exploiting the structure of the conjunctive queries using generalized hypertree decompositions of small width to factorize elements of the answer set together. We illustrate the various applications of LP(CQ) programs on three examples: optimizing deliveries of resources, minimizing noise for differential privacy, and computing the s-measure of patterns in graphs as needed for data mining.

Published
2022
Full Text
View/download PDF

2. Schema-Based Automata Determinization

Author

Niehren, Joachim, Sakho, Momar, and Serhali, Antonio Al

Subjects
Computer Science - Formal Languages and Automata Theory, Computer Science - Computational Complexity
Abstract

We propose an algorithm for schema-based determinization of finite automata on words and of step-wise hedge automata on nested words. The idea is to integrate schema-based cleaning directly into automata determinization. We prove the correctness of our new algorithm and show that it is alway smore efficient than standard determinization followed by schema-based cleaning. Our implementation permits to obtain a small deterministic automaton for an example of an XPath query, where standard determinization yields a huge stepwise hedge automaton for which schema-based cleaning runs out of memory., Comment: In Proceedings GandALF 2022, arXiv:2209.09333

Published
2022
Full Text
View/download PDF

3. Jumping Evaluation of Nested Regular Path Queries

Author

Niehren, Joachim, Salvati, Sylvain, and Azimov, Rustam

Subjects
Computer Science - Computational Complexity, Computer Science - Databases, Computer Science - Data Structures and Algorithms, Computer Science - Logic in Computer Science
Abstract

Nested regular path queries are used for querying graph databases and RDF triple stores. We propose a new algorithm for evaluating nested regular path queries on a graph from a set of start nodes in combined linear time. We show that this complexity upper bound can be reduced by making it dependent on the size of the query's top-down needed subgraph, a notion that we introduce. For many queries in practice, the top-down needed subgraph is way smaller than the whole graph. Our algorithm is based on a novel compilation schema from nested regular path queries to monadic datalog queries. Its complexity upper bound follows from known properties of top-down datalog evaluation. As an application, we show that our algorithm permits to reformulate in simple terms a variant of a very efficient automata-based algorithm proposed by Maneth and Nguyen that evaluates navigational path queries in datatrees based on indexes and jumping. Moreover, it overcomes some limitations of Maneth and Nguyen's: it is not bound to trees and applies to graphs; it is not limited to forward navigational XPath but can treat any nested regular path query and it can be implemented efficiently without any dedicated techniques, by using any efficient datalog evaluator such as LogicBlox., Comment: In Proceedings ICLP 2022, arXiv:2208.02685

Published
2022
Full Text
View/download PDF

4. Core SBML and Its Formal Semantics

Author

Niehren, Joachim, Lhoussaine, Cédric, Vaginay, Athénaïs, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Pang, Jun, editor, and Niehren, Joachim, editor

Published
2023
Full Text
View/download PDF

5. Subhedge Projection for Stepwise Hedge Automata

Author

Serhali, Antonio Al, Niehren, Joachim, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Fernau, Henning, editor, and Jansen, Klaus, editor

Published
2023
Full Text
View/download PDF

7. Proceedings Fifth International Workshop on Rewriting Techniques for Program Transformations and Evaluation

Author

Niehren, Joachim and Sabel, David

Subjects
Computer Science - Programming Languages
Abstract

This volume contains the formal proceedings of the 5th International Workshop on Rewriting Techniques for Program Transformations and Evaluation (WPTE 2018), held on 8th of Juli 2018 in Oxford, United Kingdom, and affiliated with FLoC 2018 and FSCD 2018. Scope of WPTE: Rewriting techniques are of great help for studying correctness of program transformations, translations and evaluation, and the aim of WPTE is to bring together the researchers working on program transformations, evaluation, and operationally-based programming language semantics, using rewriting methods, in order to share the techniques and recent developments and to exchange ideas to encourage further activation of research in this area. Topics in the scope of WPTE include the correctness of program transformations, optimisations and translations; program transformations for proving termination, confluence and other properties; correctness of evaluation strategies; operational semantics of programs, operationally-based program equivalences such as contextual equivalences and bisimulations; cost-models for reasoning about the optimizing power of transformations and the costs of evaluation; program transformations for verification and theorem proving purposes; translation, simulation, equivalence of programs with different formalisms, and evaluation strategies; program transformations for applying rewriting techniques to programs in specific programming languages; program transformations for program inversions and program synthesis; program transformation and evaluation for Haskell and rewriting. Research Paper Selection: At the workshop six research papers were presented of which five were accepted for the postproceedings. Each submission was reviewed by three or four members of the Program Committee in two to three rounds, one round for workshop presentation and at most two rounds for publication to the postproceedings. The program also included one invited talk by Jean-Pierre Jouannaud (Polytec, Palaiseau, Grand Paris, France) on a framework for graph rewriting; the abstract of this talk is included in this volume.

Published
2019
Full Text
View/download PDF

8. Solving linear programs on factorized databases

Author

Capelli, Florent, Crosetti, Nicolas, Niehren, Joachim, and Ramon, Jan

Subjects
Computer Science - Databases
Abstract

A typical workflow for solving a linear programming problem is to first write a linear program parametrized by the data in a language such as Math GNU Prog or AMPL then call the solver on this program while providing the data. When the data is extracted using a query on a database, this approach ignores the underlying structure of the answer set which may result in a blow-up of the size of the linear program if the answer set is big. In this paper, we study the problem of solving linear programming problems whose variables are the answers to a conjunctive query. We show that one can exploit the structure of the query to rewrite the linear program so that its size depends only on the size of the database and not on the size of the answer set. More precisely, we give a generic way of rewriting a linear program whose variables are the tuples in Q(D) for a conjunctive query Q and a database D into a linear program having a number of variables that only depends on the size of a factorized representation of Q(D), which can be much smaller when the fractional hypertree width of Q is bounded.

Published
2019

12. Abstract Simulation of Reaction Networks via Boolean Networks

Author

Niehren, Joachim, Vaginay, Athénaïs, Versari, Cristian, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Petre, Ion, editor, and Păun, Andrei, editor

Published
2022
Full Text
View/download PDF

14. Complete Subhedge Projection for Stepwise Hedge Automata †.

Author

Al Serhali, Antonio and Niehren, Joachim

Subjects
*EVALUATORS, *ALGORITHMS
Abstract

We demonstrate how to evaluate stepwise hedge automata (Shas) with subhedge projection while completely projecting irrelevant subhedges. Since this requires passing finite state information top-down, we introduce the notion of downward stepwise hedge automata. We use them to define in-memory and streaming evaluators with complete subhedge projection for Shas. We then tune the evaluators so that they can decide on membership at the earliest time point. We apply our algorithms to the problem of answering regular XPath queries on Xml streams. Our experiments show that complete subhedge projection of Shas can indeed speed up earliest query answering on Xml streams so that it becomes competitive with the best existing streaming tools for XPath queries. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

17. Computing Difference Abstractions of Metabolic Networks Under Kinetic Constraints

Author

Allart, Emilie, Niehren, Joachim, Versari, Cristian, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bortolussi, Luca, editor, and Sanguinetti, Guido, editor

Published
2019
Full Text
View/download PDF

18. Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables

Author

Boneva, Iovka, Niehren, Joachim, Sakho, Momar, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Martín-Vide, Carlos, editor, Okhotin, Alexander, editor, and Shapira, Dana, editor

Published
2019
Full Text
View/download PDF

19. Deterministic Automata for Unordered Trees

Author

Boiret, Adrien, Hugot, Vincent, Niehren, Joachim, and Treinen, Ralf

Subjects
Computer Science - Formal Languages and Automata Theory
Abstract

Automata for unordered unranked trees are relevant for defining schemas and queries for data trees in Json or Xml format. While the existing notions are well-investigated concerning expressiveness, they all lack a proper notion of determinism, which makes it difficult to distinguish subclasses of automata for which problems such as inclusion, equivalence, and minimization can be solved efficiently. In this paper, we propose and investigate different notions of "horizontal determinism", starting from automata for unranked trees in which the horizontal evaluation is performed by finite state automata. We show that a restriction to confluent horizontal evaluation leads to polynomial-time emptiness and universality, but still suffers from coNP-completeness of the emptiness of binary intersections. Finally, efficient algorithms can be obtained by imposing an order of horizontal evaluation globally for all automata in the class. Depending on the choice of the order, we obtain different classes of automata, each of which has the same expressiveness as CMso., Comment: In Proceedings GandALF 2014, arXiv:1408.5560

Published
2014
Full Text
View/download PDF

20. Certain Query Answering on Compressed String Patterns: From Streams to Hyperstreams

Author

Boneva, Iovka, Niehren, Joachim, Sakho, Momar, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Potapov, Igor, editor, and Reynier, Pierre-Alain, editor

Published
2018
Full Text
View/download PDF

22. Equivalence of Symbolic Tree Transducers

Author

Hugot, Vincent, Boiret, Adrien, Niehren, Joachim, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Charlier, Émilie, editor, Leroy, Julien, editor, and Rigo, Michel, editor

Published
2017
Full Text
View/download PDF

23. Subhedge Projection for Stepwise Hedge Automata

Author

Al Serhali, Antonio, Niehren, Joachim, Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-TT]Computer Science [cs]/Document and Text Processing, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Nested words, Query answering, Streaming, Automata
Abstract

International audience; We show how to evaluate stepwise hedge automata (SHAs) with subtree projection. Since this requires to pass finite state information top-down, we introduce the notion of downward stepwise hedge automata. We then use them in order to define an in-memory and a streaming evaluator with subhedge projection for SHAs. We tune the streaming evaluator so that it can decide membership at the earliest time point. We apply our algorithms to the problem of answering regular XPath queries on XML streams. Our experiments show that subhedge projection can indeed speed up earliest query answering on XML streams.

Published
2023

24. Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams

Author

Sebastian, Tom, Niehren, Joachim, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Freivalds, Rūsiņš Mārtiņš, editor, Engels, Gregor, editor, and Catania, Barbara, editor

Published
2016
Full Text
View/download PDF

25. Normalizing Chemical Reaction Networks by Confluent Structural Simplification

Author

Madelaine, Guillaume, Tonello, Elisa, Lhoussaine, Cédric, Niehren, Joachim, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bartocci, Ezio, editor, Lio, Pietro, editor, and Paoletti, Nicola, editor

Published
2016
Full Text
View/download PDF

27. LINEAR PROGRAMS WITH CONJUNCTIVE DATABASE QUERIES.

Author

CAPELLI, FLORENT, CROSETTI, NICOLAS, NIEHREN, JOACHIM, and RAMON, JAN

Subjects
DATABASES, DATA mining
Abstract

In this paper, we study the problem of optimizing a linear program whose variables are the answers to a conjunctive query. For this we propose the language LP(CQ) for specifying linear programs whose constraints and objective functions depend on the answer sets of conjunctive queries. We contribute an efficient algorithm for solving programs in a fragment of LP(CQ). The natural approach constructs a linear program having as many variables as there are elements in the answer set of the queries. Our approach constructs a linear program having the same optimal value but fewer variables. This is done by exploiting the structure of the conjunctive queries using generalized hypertree decompositions of small width to factorize elements of the answer set together. We illustrate the various applications of LP(CQ) programs on three examples: optimizing deliveries of resources, minimizing noise for differential privacy, and computing the s-measure of patterns in graphs as needed for data mining. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

30. Weak subsumption Constraints for Type Diagnosis: An Incremental Algorithm

Author

Mueller, Martin and Niehren, Joachim

Subjects
Computer Science - Computation and Language
Abstract

We introduce constraints necessary for type checking a higher-order concurrent constraint language, and solve them with an incremental algorithm. Our constraint system extends rational unification by constraints x$\subseteq$ y saying that ``$x$ has at least the structure of $y$'', modelled by a weak instance relation between trees. This notion of instance has been carefully chosen to be weaker than the usual one which renders semi-unification undecidable. Semi-unification has more than once served to link unification problems arising from type inference and those considered in computational linguistics. Just as polymorphic recursion corresponds to subsumption through the semi-unification problem, our type constraint problem corresponds to weak subsumption of feature graphs in linguistics. The decidability problem for \WhatsIt for feature graphs has been settled by D\"orre~\cite{Doerre:WeakSubsumption:94}. \nocite{RuppRosnerJohnson:94} In contrast to D\"orre's, our algorithm is fully incremental and does not refer to finite state automata. Our algorithm also is a lot more flexible. It allows a number of extensions (records, sorts, disjunctive types, type declarations, and others) which make it suitable for type inference of a full-fledged programming language., Comment: Presented at CLNLP'95. An improved version is available under the name "A Type is a Type is a Type" from the Authors

Published
1995

33. A Uniform Programmning Language for Implementing XML Standards

Author

Labath, Pavel, Niehren, Joachim, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Italiano, Giuseppe F., editor, Margaria-Steffen, Tiziana, editor, Pokorný, Jaroslav, editor, Quisquater, Jean-Jacques, editor, and Wattenhofer, Roger, editor

Published
2015
Full Text
View/download PDF

36. Sublinear DTD Validity

Author

Ndione, Antoine, Lemay, Aurélien, Niehren, Joachim, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Dediu, Adrian-Horia, editor, Formenti, Enrico, editor, Martín-Vide, Carlos, editor, and Truthe, Bianca, editor

Published
2015
Full Text
View/download PDF

37. Logics for Unordered Trees with Data Constraints on Siblings

Author

Boiret, Adrien, Hugot, Vincent, Niehren, Joachim, Treinen, Ralf, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Dediu, Adrian-Horia, editor, Formenti, Enrico, editor, Martín-Vide, Carlos, editor, and Truthe, Bianca, editor

Published
2015
Full Text
View/download PDF

38. Attractor Equivalence: An Observational Semantics for Reaction Networks

Author

Madelaine, Guillaume, Lhoussaine, Cédric, Niehren, Joachim, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Istrail, Sorin, Series editor, Pevzner, Pavel, Series editor, Waterman, Michael S., Series editor, Fages, François, editor, and Piazza, Carla, editor

Published
2014
Full Text
View/download PDF

39. Learning Sequential Tree-to-Word Transducers

Author

Laurence, Grégoire, Lemay, Aurélien, Niehren, Joachim, Staworko, Sławek, Tommasi, Marc, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Dediu, Adrian-Horia, editor, Martín-Vide, Carlos, editor, Sierra-Rodríguez, José-Luis, editor, and Truthe, Bianca, editor

Published
2014
Full Text
View/download PDF

42. Early Nested Word Automata for XPath Query Answering on XML Streams

Author

Debarbieux, Denis, Gauwin, Olivier, Niehren, Joachim, Sebastian, Tom, Zergaoui, Mohamed, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Konstantinidis, Stavros, editor

Published
2013
Full Text
View/download PDF

43. Knockout Prediction for Reaction Networks with Partial Kinetic Information

Author

John, Mathias, Nebut, Mirabelle, Niehren, Joachim, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Giacobazzi, Roberto, editor, Berdine, Josh, editor, and Mastroeni, Isabella, editor

Published
2013
Full Text
View/download PDF

44. Learning Rational Functions

Author

Boiret, Adrien, Lemay, Aurélien, Niehren, Joachim, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Yen, Hsu-Chun, editor, and Ibarra, Oscar H., editor

Published
2012
Full Text
View/download PDF

45. Streamable Fragments of Forward XPath

Author

Gauwin, Olivier, Niehren, Joachim, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Bouchou-Markhoff, Béatrice, editor, Caron, Pascal, editor, Champarnaud, Jean-Marc, editor, and Maurel, Denis, editor

Published
2011
Full Text
View/download PDF

46. Normalization of Sequential Top-Down Tree-to-Word Transducers

Author

Laurence, Grégoire, Lemay, Aurélien, Niehren, Joachim, Staworko, Sławek, Tommasi, Marc, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Dediu, Adrian-Horia, editor, Inenaga, Shunsuke, editor, and Martín-Vide, Carlos, editor

Published
2011
Full Text
View/download PDF

47. Biochemical Reaction Rules with Constraints

Author

John, Mathias, Lhoussaine, Cédric, Niehren, Joachim, Versari, Cristian, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Barthe, Gilles, editor

Published
2011
Full Text
View/download PDF

48. Jumping Evaluation of Nested Regular Path Queries

Author

Azimov, Rustam, Niehren, Joachim, Salvati, Sylvain, Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Saint Petersburg State University (SPBU), The research was supported by the Russian Science Foundation grant 18-11-00100., Saint Petersburg State University [SPBU], Linking Dynamic Data [LINKS], Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189 (CRIStAL), Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
FOS: Computer and information sciences, Computer Science - Computational Complexity, Computer Science - Logic in Computer Science, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Computer Science - Databases, Computer Science - Data Structures and Algorithms, InformationSystems_DATABASEMANAGEMENT, Databases (cs.DB), Data Structures and Algorithms (cs.DS), Computational Complexity (cs.CC), Logic in Computer Science (cs.LO)
Abstract

Nested regular path queries are used for querying graph databases and RDF triple stores. We propose a new algorithm for evaluating nested regular path queries on a graph from a set of start nodes in combined linear time. We show that this complexity upper bound can be reduced by making it dependent on the size of the query's top-down needed subgraph, a notion that we introduce. For many queries in practice, the top-down needed subgraph is way smaller than the whole graph. Our algorithm is based on a novel compilation schema from nested regular path queries to monadic datalog queries. Its complexity upper bound follows from known properties of top-down datalog evaluation. As an application, we show that our algorithm permits to reformulate in simple terms a variant of a very efficient automata-based algorithm proposed by Maneth and Nguyen that evaluates navigational path queries in datatrees based on indexes and jumping. Moreover, it overcomes some limitations of Maneth and Nguyen's: it is not bound to trees and applies to graphs; it is not limited to forward navigational XPath but can treat any nested regular path query and it can be implemented efficiently without any dedicated techniques, by using any efficient datalog evaluator such as LogicBlox., In Proceedings ICLP 2022, arXiv:2208.02685

Published
2022

Catalog

Books, media, physical & digital resources
See catalog results