6 Search Results for "Martens, Jean-Pierre"

Document
DOI: 10.4230/LIPIcs.CONCUR.2023.32
Computing Minimal Distinguishing Hennessy-Milner Formulas is NP-Hard, but Variants are Tractable

Authors: Jan Martens and Jan Friso Groote

Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)

Abstract
We study the problem of computing minimal distinguishing formulas for non-bisimilar states in finite LTSs. We show that this is NP-hard if the size of the formula must be minimal. Similarly, the existence of a short distinguishing trace is NP-complete. However, we can provide polynomial algorithms, if minimality is formulated as the minimal number of nested modalities, and it can even be extended by recursively requiring a minimal number of nested negations. A prototype implementation shows that the generated formulas are much smaller than those generated by the method introduced by Cleaveland.
Cite as

Jan Martens and Jan Friso Groote. Computing Minimal Distinguishing Hennessy-Milner Formulas is NP-Hard, but Variants are Tractable. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{martens_et_al:LIPIcs.CONCUR.2023.32,
  author =	{Martens, Jan and Groote, Jan Friso},
  title =	{{Computing Minimal Distinguishing Hennessy-Milner Formulas is NP-Hard, but Variants are Tractable}},
  booktitle =	{34th International Conference on Concurrency Theory (CONCUR 2023)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-299-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{279},
  editor =	{P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.32},
  URN =		{urn:nbn:de:0030-drops-190268},
  doi =		{10.4230/LIPIcs.CONCUR.2023.32},
  annote =	{Keywords: Distinguishing behaviour, Hennessy-Milner logic, NP-hardness}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICDT.2020.3
Current Challenges in Graph Databases (Invited Talk)

Authors: Juan L. Reutter

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract
As graph databases grow in popularity, decades of work in graph query languages and models are materialising in industry standards and in the construction of new graph database systems. However, this surge in graph systems has in turn opened up a series of new, interesting research problems related to graph databases. Our first set of problems has to do with more efficient ways of computing the answers of graph queries, specifically graph patterns, path queries, and combinations between them. Traditionally, researchers in graph databases have pointed out that relational systems are ill-equipped to process these types of queries, and if one looks at the performance of native graph database systems, there is clearly a lot of room for improvement. The talk focuses on two possible directions for improving the state of the art in graph query processing. The first is implementing worst-case optimal algorithms for processing graph patterns that traduce in relational queries with several joins. Some advances are already in development (see e.g. Nguyen, Dung, et al. "Join processing for graph patterns: An old dog with new tricks." GRADES'15. or Hogan, Aidan, et al. "A Worst-Case Optimal Join Algorithm for SPARQL." ISWC’19.), but we are still far from a full fledged solution: most algorithms require complex data structures, or need further support in terms of heuristics to select an order in which joins are processed. Second, we need to understand what is the best way of evaluating path queries (that is, finding all pairs of nodes connected by a path), in such a way that these results can be further integrated with other query results in a graph system pipeline. We already have complexity results regarding path computation and enumeration for different semantics of path queries (see e.g. Martens, Wim, and Tina Trautner. "Evaluation and enumeration problems for regular path queries." ICDT'18. or Bagan, Guillaume, Angela Bonifati, and Benoit Groz. "A trichotomy for regular simple path queries on graphs." PODS'13.), but still very little is known in terms of optimal processing of path queries when inside a tractable fragment. Our second set of problems is related to graph analytics, one of the current selling points of graph databases. Systems should be able to run more complex analytical queries involving tasks such as more complex path finding, centrality or clustering. It is also important to be able to run these algorithms not over native graphs, but perhaps over a certain set of nodes or edges previously selected by a graph query, and one may also want to pose further queries over the result of the analytics task. Finally, all of this should be done in an efficient way, specially in the prospect that graph databases may contain a huge amount of nodes. In this talk I will discuss possible approaches to perform these operations, covering aspects from the design of languages for graph analytics to efficient ways of processing them, and also comparing the expressive power of graph analytics solutions with other forms of graph computation.
Cite as

Juan L. Reutter. Current Challenges in Graph Databases (Invited Talk). In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{reutter:LIPIcs.ICDT.2020.3,
  author =	{Reutter, Juan L.},
  title =	{{Current Challenges in Graph Databases}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.3},
  URN =		{urn:nbn:de:0030-drops-119272},
  doi =		{10.4230/LIPIcs.ICDT.2020.3},
  annote =	{Keywords: Graph databases, Join algorithms, path queries, graph analytics}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2020.8
Weight Annotation in Information Extraction

Authors: Johannes Doleschal, Benny Kimelfeld, Wim Martens, and Liat Peterfreund

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract
The framework of document spanners abstracts the task of information extraction from text as a function that maps every document (a string) into a relation over the document’s spans (intervals identified by their start and end indices). For instance, the regular spanners are the closure under the Relational Algebra (RA) of the regular expressions with capture variables, and the expressive power of the regular spanners is precisely captured by the class of vset-automata - a restricted class of transducers that mark the endpoints of selected spans. In this work, we embark on the investigation of document spanners that can annotate extractions with auxiliary information such as confidence, support, and confidentiality measures. To this end, we adopt the abstraction of provenance semirings by Green et al., where tuples of a relation are annotated with the elements of a commutative semiring, and where the annotation propagates through the (positive) RA operators via the semiring operators. Hence, the proposed spanner extension, referred to as an annotator, maps every string into an annotated relation over the spans. As a specific instantiation, we explore weighted vset-automata that, similarly to weighted automata and transducers, attach semiring elements to transitions. We investigate key aspects of expressiveness, such as the closure under the positive RA, and key aspects of computational complexity, such as the enumeration of annotated answers and their ranked enumeration in the case of numeric semirings. For a number of these problems, fundamental properties of the underlying semiring, such as positivity, are crucial for establishing tractability.
Cite as

Johannes Doleschal, Benny Kimelfeld, Wim Martens, and Liat Peterfreund. Weight Annotation in Information Extraction. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{doleschal_et_al:LIPIcs.ICDT.2020.8,
  author =	{Doleschal, Johannes and Kimelfeld, Benny and Martens, Wim and Peterfreund, Liat},
  title =	{{Weight Annotation in Information Extraction}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.8},
  URN =		{urn:nbn:de:0030-drops-119325},
  doi =		{10.4230/LIPIcs.ICDT.2020.8},
  annote =	{Keywords: Information extraction, regular document spanners, weighted automata, provenance semirings, K-relations}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.7
A Trichotomy for Regular Trail Queries

Authors: Wim Martens, Matthias Niewerth, and Tina Trautner

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Regular path queries (RPQs) are an essential component of graph query languages. Such queries consider a regular expression r and a directed edge-labeled graph G and search for paths in G for which the sequence of labels is in the language of r. In order to avoid having to consider infinitely many paths, some database engines restrict such paths to be trails, that is, they only consider paths without repeated edges. In this paper we consider the evaluation problem for RPQs under trail semantics, in the case where the expression is fixed. We show that, in this setting, there exists a trichotomy. More precisely, the complexity of RPQ evaluation divides the regular languages into the finite languages, the class T_tract (for which the problem is tractable), and the rest. Interestingly, the tractable class in the trichotomy is larger than for the trichotomy for simple paths, discovered by Bagan et al. [Bagan et al., 2013]. In addition to this trichotomy result, we also study characterizations of the tractable class, its expressivity, the recognition problem, closure properties, and show how the decision problem can be extended to the enumeration problem, which is relevant to practice.
Cite as

Wim Martens, Matthias Niewerth, and Tina Trautner. A Trichotomy for Regular Trail Queries. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{martens_et_al:LIPIcs.STACS.2020.7,
  author =	{Martens, Wim and Niewerth, Matthias and Trautner, Tina},
  title =	{{A Trichotomy for Regular Trail Queries}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.7},
  URN =		{urn:nbn:de:0030-drops-118681},
  doi =		{10.4230/LIPIcs.STACS.2020.7},
  annote =	{Keywords: Regular languages, query languages, path queries, graph databases, databases, complexity, trails, simple paths}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2016.10
A Formal Study of Collaborative Access Control in Distributed Datalog

Authors: Serge Abiteboul, Pierre Bourhis, and Victor Vianu

Published in: LIPIcs, Volume 48, 19th International Conference on Database Theory (ICDT 2016)

Abstract
We formalize and study a declaratively specified collaborative access control mechanism for data dissemination in a distributed environment. Data dissemination is specified using distributed datalog. Access control is also defined by datalog-style rules, at the relation level for extensional relations, and at the tuple level for intensional ones, based on the derivation of tuples. The model also includes a mechanism for "declassifying" data, that allows circumventing overly restrictive access control. We consider the complexity of determining whether a peer is allowed to access a given fact, and address the problem of achieving the goal of disseminating certain information under some access control policy. We also investigate the problem of information leakage, which occurs when a peer is able to infer facts to which the peer is not allowed access by the policy. Finally, we consider access control extended to facts equipped with provenance information, motivated by the many applications where such information is required. We provide semantics for access control with provenance, and establish the complexity of determining whether a peer may access a given fact together with its provenance. This work is motivated by the access control of the Webdamlog system, whose core features it formalizes.
Cite as

Serge Abiteboul, Pierre Bourhis, and Victor Vianu. A Formal Study of Collaborative Access Control in Distributed Datalog. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{abiteboul_et_al:LIPIcs.ICDT.2016.10,
  author =	{Abiteboul, Serge and Bourhis, Pierre and Vianu, Victor},
  title =	{{A Formal Study of Collaborative Access Control in Distributed Datalog}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Martens, Wim and Zeume, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2016.10},
  URN =		{urn:nbn:de:0030-drops-57794},
  doi =		{10.4230/LIPIcs.ICDT.2016.10},
  annote =	{Keywords: Distributed datalog, access control, provenance}
}
Document
DOI: 10.4230/DagSemProc.06171.3
A User-Oriented Approach to Music Information Retrieval

Authors: Micheline Lesaffre, Marc Leman, and Jean-Pierre Martens

Published in: Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006)

Abstract
Search and retrieval of specific musical content (e.g. emotion, melody) has become an important aspect of system development but only little research is user-oriented. The success of music information retrieval technology primarily depends on both assessing and meeting the needs of its users. Potential users of music information retrieval systems, however, draw upon various ways of expressing themselves. But, who are the potential users of MIR systems and how would they describe music qualities? High-level concepts contribute to the definition of meaning in music. How can we measure meaning and emotion in music? How can we define the higher-order understanding of features of music that the average users share? Information on listener’s perception of qualities of music is needed to make automated access to music content attractive to system users. The emphasis of our investigation is on a user-oriented approach to the semantic description of music. We report the results of an experiment that explores how users perceive affects in music, and what structural descriptions of music best characterize their understanding of music expression. 79 potential users of music information retrieval systems rated different sets of adjectives, while they were listening to 160 pieces of real music. The subject group (79) was recruited amongst 774 participants in a large survey on the music background, habits and interests, preferred genres, taste and favourite titles of people who are willing to use interactive music systems. Moreover, the stimuli used reflected the musical taste of the average participant in the large survey (774). The study reveals that perceived qualities of music are affected by the profile of the user. Significant subject dependencies are found for age, music expertise, musicianship, broadness of taste and familiarity with classical music. Furthermore, interesting relationships are discovered between expressive and structural features. Analyses show that the targeted population most unanimously agrees on loudness and tempo, whilst less unanimity was found for timbre and articulation. Finally, our findings are tested and validated by means of a demo of a semantic music recommender system prototype that supports the querying of a music database by semantic descriptors for affect, structure and motion. The system, that recommends music from a relational database containing the quality ratings provided by the participants, illustrates the potential of a user-dependent and emotion-based retrieval of music.
Cite as

Micheline Lesaffre, Marc Leman, and Jean-Pierre Martens. A User-Oriented Approach to Music Information Retrieval. In Content-Based Retrieval. Dagstuhl Seminar Proceedings, Volume 6171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{lesaffre_et_al:DagSemProc.06171.3,
  author =	{Lesaffre, Micheline and Leman, Marc and Martens, Jean-Pierre},
  title =	{{A User-Oriented Approach to Music Information Retrieval}},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.3},
  URN =		{urn:nbn:de:0030-drops-6509},
  doi =		{10.4230/DagSemProc.06171.3},
  annote =	{Keywords: Semantic description, user studies, music information retrieval}
}
  • Refine by Author
  • 2 Martens, Wim
  • 1 Abiteboul, Serge
  • 1 Bourhis, Pierre
  • 1 Doleschal, Johannes
  • 1 Groote, Jan Friso
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Information systems → Information extraction
  • 1 Information systems → Information retrieval query processing
  • 1 Information systems → Query languages for non-relational engines
  • 1 Theory of computation → Data provenance
  • Show More...

  • Refine by Keyword
  • 2 path queries
  • 1 Distinguishing behaviour
  • 1 Distributed datalog
  • 1 Graph databases
  • 1 Hennessy-Milner logic
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2020
  • 1 2006
  • 1 2016
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact