22 Search Results for "Bollansée, Pablo"

Document
DOI: 10.4230/LIPIcs.MFCS.2023.17
Separating Automatic Relations

Authors: Pablo Barceló, Diego Figueira, and Rémi Morvan

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We study the separability problem for automatic relations (i.e., relations on finite words definable by synchronous automata) in terms of recognizable relations (i.e., finite unions of products of regular languages). This problem takes as input two automatic relations R and R', and asks if there exists a recognizable relation S that contains R and does not intersect R'. We show this problem to be undecidable when the number of products allowed in the recognizable relation is fixed. In particular, checking if there exists a recognizable relation S with at most k products of regular languages that separates R from R' is undecidable, for each fixed k ⩾ 2. Our proofs reveal tight connections, of independent interest, between the separability problem and the finite coloring problem for automatic graphs, where colors are regular languages.
Cite as

Pablo Barceló, Diego Figueira, and Rémi Morvan. Separating Automatic Relations. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{barcelo_et_al:LIPIcs.MFCS.2023.17,
  author =	{Barcel\'{o}, Pablo and Figueira, Diego and Morvan, R\'{e}mi},
  title =	{{Separating Automatic Relations}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.17},
  URN =		{urn:nbn:de:0030-drops-185514},
  doi =		{10.4230/LIPIcs.MFCS.2023.17},
  annote =	{Keywords: Automatic relations, recognizable relations, separability, finite colorability}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2023.11
Two Decreasing Measures for Simply Typed λ-Terms

Authors: Pablo Barenbaum and Cristian Sottile

Published in: LIPIcs, Volume 260, 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)

Abstract
This paper defines two decreasing measures for terms of the simply typed λ-calculus, called the 𝒲-measure and the 𝒯^{𝐦}-measure. A decreasing measure is a function that maps each typable λ-term to an element of a well-founded ordering, in such a way that contracting any β-redex decreases the value of the function, entailing strong normalization. Both measures are defined constructively, relying on an auxiliary calculus, a non-erasing variant of the λ-calculus. In this system, dubbed the λ^{𝐦}-calculus, each β-step creates a "wrapper" containing a copy of the argument that cannot be erased and cannot interact with the context in any other way. Both measures rely crucially on the observation, known to Turing and Prawitz, that contracting a redex cannot create redexes of higher degree, where the degree of a redex is defined as the height of the type of its λ-abstraction. The 𝒲-measure maps each λ-term to a natural number, and it is obtained by evaluating the term in the λ^{𝐦}-calculus and counting the number of remaining wrappers. The 𝒯^{𝐦}-measure maps each λ-term to a structure of nested multisets, where the nesting depth is proportional to the maximum redex degree.
Cite as

Pablo Barenbaum and Cristian Sottile. Two Decreasing Measures for Simply Typed λ-Terms. In 8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 260, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{barenbaum_et_al:LIPIcs.FSCD.2023.11,
  author =	{Barenbaum, Pablo and Sottile, Cristian},
  title =	{{Two Decreasing Measures for Simply Typed \lambda-Terms}},
  booktitle =	{8th International Conference on Formal Structures for Computation and Deduction (FSCD 2023)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-277-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{260},
  editor =	{Gaboardi, Marco and van Raamsdonk, Femke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2023.11},
  URN =		{urn:nbn:de:0030-drops-179956},
  doi =		{10.4230/LIPIcs.FSCD.2023.11},
  annote =	{Keywords: Lambda Calculus, Rewriting, Termination, Strong Normalization, Simple Types}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2023.15
Approximation and Semantic Tree-Width of Conjunctive Regular Path Queries

Authors: Diego Figueira and Rémi Morvan

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
We show that the problem of whether a query is equivalent to a query of tree-width k is decidable, for the class of Unions of Conjunctive Regular Path Queries with two-way navigation (UC2RPQs). A previous result by Barceló, Romero, and Vardi [Pablo Barceló et al., 2016] has shown decidability for the case k = 1, and here we show that decidability in fact holds for any arbitrary k > 1. The algorithm is in 2ExpSpace, but for the restricted but practically relevant case where all regular expressions of the query are of the form a^* or (a_1 + ... + a_n) we show that the complexity of the problem drops to Π^p_2. We also investigate the related problem of approximating a UC2RPQ by queries of small tree-width. We exhibit an algorithm which, for any fixed number k, builds the maximal under-approximation of tree-width k of a UC2RPQ. The maximal under-approximation of tree-width k of a query q is a query q' of tree-width k which is contained in q in a maximal and unique way, that is, such that for every query q'' of tree-width k, if q'' is contained in q then q'' is also contained in q'.
Cite as

Diego Figueira and Rémi Morvan. Approximation and Semantic Tree-Width of Conjunctive Regular Path Queries. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{figueira_et_al:LIPIcs.ICDT.2023.15,
  author =	{Figueira, Diego and Morvan, R\'{e}mi},
  title =	{{Approximation and Semantic Tree-Width of Conjunctive Regular Path Queries}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.15},
  URN =		{urn:nbn:de:0030-drops-177575},
  doi =		{10.4230/LIPIcs.ICDT.2023.15},
  annote =	{Keywords: graph databases, conjunctive regular path queries, semantic optimization, tree-width, containment, approximation}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.20
Computing Power of Hybrid Models in Synchronous Networks

Authors: Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. The separation results are obtained by approaching communication complexity through an original angle, which may be of an independent interest. The two players are not bounded to compute the value of a binary function, but the combined outputs of the two players are constrained by this value. In particular, we introduce the XOR-Index problem, in which Alice is given a binary vector x ∈ {0,1}ⁿ together with an index i ∈ [n], Bob is given a binary vector y ∈ {0,1}ⁿ together with an index j ∈ [n], and, after a single round of 2-way communication, Alice must output a boolean out_A, and Bob must output a boolean out_B, such that out_A ∧ out_B = x_j⊕ y_i. We show that the communication complexity of XOR-Index is Ω(n) bits.
Cite as

Pierre Fraigniaud, Pedro Montealegre, Pablo Paredes, Ivan Rapaport, Martín Ríos-Wilson, and Ioan Todinca. Computing Power of Hybrid Models in Synchronous Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.OPODIS.2022.20,
  author =	{Fraigniaud, Pierre and Montealegre, Pedro and Paredes, Pablo and Rapaport, Ivan and R{\'\i}os-Wilson, Mart{\'\i}n and Todinca, Ioan},
  title =	{{Computing Power of Hybrid Models in Synchronous Networks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.20},
  URN =		{urn:nbn:de:0030-drops-176401},
  doi =		{10.4230/LIPIcs.OPODIS.2022.20},
  annote =	{Keywords: hybrid model, synchronous networks, LOCAL, CONGEST, Broadcast Congested Clique}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.9
Universal Gauge-Invariant Cellular Automata

Authors: Pablo Arrighi, Marin Costes, and Nathanaël Eon

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Gauge symmetries play a fundamental role in Physics, as they provide a mathematical justification for the fundamental forces. Usually, one starts from a non-interactive theory which governs "matter", and features a global symmetry. One then extends the theory so as make the global symmetry into a local one (a.k.a gauge-invariance). We formalise a discrete counterpart of this process, known as gauge extension, within the Computer Science framework of Cellular Automata (CA). We prove that the CA which admit a relative gauge extension are exactly the globally symmetric ones (a.k.a the colour-blind). We prove that any CA admits a non-relative gauge extension. Both constructions yield universal gauge-invariant CA, but the latter allows for a first example where the gauge extension mediates interactions within the initial CA.
Cite as

Pablo Arrighi, Marin Costes, and Nathanaël Eon. Universal Gauge-Invariant Cellular Automata. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arrighi_et_al:LIPIcs.MFCS.2021.9,
  author =	{Arrighi, Pablo and Costes, Marin and Eon, Nathana\"{e}l},
  title =	{{Universal Gauge-Invariant Cellular Automata}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.9},
  URN =		{urn:nbn:de:0030-drops-144490},
  doi =		{10.4230/LIPIcs.MFCS.2021.9},
  annote =	{Keywords: Cellular automata, Gauge-invariance, Universality}
}
Document
DOI: 10.4230/OASIcs.SLATE.2021.10
LeMe-PT: A Medical Package Leaflet Corpus for Portuguese

Authors: Alberto Simões and Pablo Gamallo

Published in: OASIcs, Volume 94, 10th Symposium on Languages, Applications and Technologies (SLATE 2021)

Abstract
The current trend on natural language processing is the use of machine learning. This is being done on every field, from summarization to machine translation. For these techniques to be applied, resources are needed, namely quality corpora. While there are large quantities of corpora for the Portuguese language, there is the lack of technical and focused corpora. Therefore, in this article we present a new corpus, built from drug package leaflets. We describe its structure and contents, and discuss possible exploration directions.
Cite as

Alberto Simões and Pablo Gamallo. LeMe-PT: A Medical Package Leaflet Corpus for Portuguese. In 10th Symposium on Languages, Applications and Technologies (SLATE 2021). Open Access Series in Informatics (OASIcs), Volume 94, pp. 10:1-10:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{simoes_et_al:OASIcs.SLATE.2021.10,
  author =	{Sim\~{o}es, Alberto and Gamallo, Pablo},
  title =	{{LeMe-PT: A Medical Package Leaflet Corpus for Portuguese}},
  booktitle =	{10th Symposium on Languages, Applications and Technologies (SLATE 2021)},
  pages =	{10:1--10:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-202-0},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{94},
  editor =	{Queir\'{o}s, Ricardo and Pinto, M\'{a}rio and Sim\~{o}es, Alberto and Portela, Filipe and Pereira, Maria Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2021.10},
  URN =		{urn:nbn:de:0030-drops-144277},
  doi =		{10.4230/OASIcs.SLATE.2021.10},
  annote =	{Keywords: drug corpora, information extractiom, word embeddings}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.4
Two Arithmetical Sources and Their Associated Tries

Authors: Valérie Berthé, Eda Cesaratto, Frédéric Paccaut, Pablo Rotondo, Martín D. Safe, and Brigitte Vallée

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
This article is devoted to the study of two arithmetical sources associated with classical partitions, that are both defined through the mediant of two fractions. The Stern-Brocot source is associated with the sequence of all the mediants, while the Sturm source only keeps mediants whose denominator is "not too large". Even though these sources are both of zero Shannon entropy, with very similar Renyi entropies, their probabilistic features yet appear to be quite different. We then study how they influence the behaviour of tries built on words they emit, and we notably focus on the trie depth. The paper deals with Analytic Combinatorics methods, and Dirichlet generating functions, that are usually used and studied in the case of good sources with positive entropy. To the best of our knowledge, the present study is the first one where these powerful methods are applied to a zero-entropy context. In our context, the generating function associated with each source is explicit and related to classical functions in Number Theory, as the ζ function, the double ζ function or the transfer operator associated with the Gauss map. We obtain precise asymptotic estimates for the mean value of the trie depth that prove moreover to be quite different for each source. Then, these sources provide explicit and natural instances which lead to two unusual and different trie behaviours.
Cite as

Valérie Berthé, Eda Cesaratto, Frédéric Paccaut, Pablo Rotondo, Martín D. Safe, and Brigitte Vallée. Two Arithmetical Sources and Their Associated Tries. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.AofA.2020.4,
  author =	{Berth\'{e}, Val\'{e}rie and Cesaratto, Eda and Paccaut, Fr\'{e}d\'{e}ric and Rotondo, Pablo and Safe, Mart{\'\i}n D. and Vall\'{e}e, Brigitte},
  title =	{{Two Arithmetical Sources and Their Associated Tries}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.4},
  URN =		{urn:nbn:de:0030-drops-120345},
  doi =		{10.4230/LIPIcs.AofA.2020.4},
  annote =	{Keywords: Combinatorics of words, Information Theory, Probabilistic analysis, Analytic combinatorics, Dirichlet generating functions, Sources, Partitions, Trie structure, Continued fraction expansion, Farey map, Sturm words, Transfer operator}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2020.6
On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra

Authors: Pablo Barceló, Nelson Higuera, Jorge Pérez, and Bernardo Subercaseaux

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

Abstract
We study the expressive power of the Lara language - a recently proposed unified model for expressing relational and linear algebra operations - both in terms of traditional database query languages and some analytic tasks often performed in machine learning pipelines. We start by showing Lara to be expressive complete with respect to first-order logic with aggregation. Since Lara is parameterized by a set of user-defined functions which allow to transform values in tables, the exact expressive power of the language depends on how these functions are defined. We distinguish two main cases depending on the level of genericity queries are enforced to satisfy. Under strong genericity assumptions the language cannot express matrix convolution, a very important operation in current machine learning operations. This language is also local, and thus cannot express operations such as matrix inverse that exhibit a recursive behavior. For expressing convolution, one can relax the genericity requirement by adding an underlying linear order on the domain. This, however, destroys locality and turns the expressive power of the language much more difficult to understand. In particular, although under complexity assumptions the resulting language can still not express matrix inverse, a proof of this fact without such assumptions seems challenging to obtain.
Cite as

Pablo Barceló, Nelson Higuera, Jorge Pérez, and Bernardo Subercaseaux. On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barcelo_et_al:LIPIcs.ICDT.2020.6,
  author =	{Barcel\'{o}, Pablo and Higuera, Nelson and P\'{e}rez, Jorge and Subercaseaux, Bernardo},
  title =	{{On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{6:1--6:20},
  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.6},
  URN =		{urn:nbn:de:0030-drops-119305},
  doi =		{10.4230/LIPIcs.ICDT.2020.6},
  annote =	{Keywords: languages for linear and relational algebra, expressive power, first order logic with aggregation, matrix convolution, matrix inverse, query genericity, locality of queries, safety}
}
Document
DOI: 10.4230/OASIcs.SLATE.2019.20
Identifying Causal Relations in Legal Documents with Dependency Syntactic Analysis

Authors: Pablo Gamallo, Patricia Martín-Rodilla, and Beatriz Calderón

Published in: OASIcs, Volume 74, 8th Symposium on Languages, Applications and Technologies (SLATE 2019)

Abstract
This article describes a method for enriching a dependency-based parser with causal connectors. Our specific objective is to identify causal relationships between elementary discourse units in Spanish legal texts. For this purpose, the approach we follow is to search for specific discourse connectives which are taken as causal dependencies relating an effect event (head) with a verbal or nominal cause (dependent). As a result, we turn a specific syntactic parser into a discourse parser aimed at recognizing causal structures.
Cite as

Pablo Gamallo, Patricia Martín-Rodilla, and Beatriz Calderón. Identifying Causal Relations in Legal Documents with Dependency Syntactic Analysis. In 8th Symposium on Languages, Applications and Technologies (SLATE 2019). Open Access Series in Informatics (OASIcs), Volume 74, pp. 20:1-20:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gamallo_et_al:OASIcs.SLATE.2019.20,
  author =	{Gamallo, Pablo and Mart{\'\i}n-Rodilla, Patricia and Calder\'{o}n, Beatriz},
  title =	{{Identifying Causal Relations in Legal Documents with Dependency Syntactic Analysis}},
  booktitle =	{8th Symposium on Languages, Applications and Technologies (SLATE 2019)},
  pages =	{20:1--20:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-114-6},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{74},
  editor =	{Rodrigues, Ricardo and Janou\v{s}ek, Jan and Ferreira, Lu{\'\i}s and Coheur, Lu{\'\i}sa and Batista, Fernando and Gon\c{c}alo Oliveira, Hugo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2019.20},
  URN =		{urn:nbn:de:0030-drops-108870},
  doi =		{10.4230/OASIcs.SLATE.2019.20},
  annote =	{Keywords: Dependency Analysis, Discourse Analysis, Causal Markers, Legal Documents}
}
Document
DOI: 10.4230/LIPIcs.CPM.2019.19
Dichotomic Selection on Words: A Probabilistic Analysis

Authors: Ali Akhavi, Julien Clément, Dimitri Darthenay, Loïck Lhote, and Brigitte Vallée

Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)

Abstract
The paper studies the behaviour of selection algorithms that are based on dichotomy principles. On the entry formed by an ordered list L and a searched element x not in L, they return the interval of the list L the element x belongs to. We focus here on the case of words, where dichotomy principles lead to a selection algorithm designed by Crochemore, Hancart and Lecroq, which appears to be "quasi-optimal". We perform a probabilistic analysis of this algorithm that exhibits its quasi-optimality on average.
Cite as

Ali Akhavi, Julien Clément, Dimitri Darthenay, Loïck Lhote, and Brigitte Vallée. Dichotomic Selection on Words: A Probabilistic Analysis. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{akhavi_et_al:LIPIcs.CPM.2019.19,
  author =	{Akhavi, Ali and Cl\'{e}ment, Julien and Darthenay, Dimitri and Lhote, Lo\"{i}ck and Vall\'{e}e, Brigitte},
  title =	{{Dichotomic Selection on Words: A Probabilistic Analysis}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Pisanti, Nadia and P. Pissis, Solon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.19},
  URN =		{urn:nbn:de:0030-drops-104903},
  doi =		{10.4230/LIPIcs.CPM.2019.19},
  annote =	{Keywords: dichotomic selection, text algorithms, analysis of algorithms, average case analysis of algorithms, trie, suffix array, lcp-array, information theory, numeration process, sources, entropy, coincidence, analytic combinatorics, depoissonization techniques}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.6
A Formal Framework for Probabilistic Unclean Databases

Authors: Christopher De Sa, Ihab F. Ilyas, Benny Kimelfeld, Christopher Ré, and Theodoros Rekatsinas

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
Most theoretical frameworks that focus on data errors and inconsistencies follow logic-based reasoning. Yet, practical data cleaning tools need to incorporate statistical reasoning to be effective in real-world data cleaning tasks. Motivated by empirical successes, we propose a formal framework for unclean databases, where two types of statistical knowledge are incorporated: The first represents a belief of how intended (clean) data is generated, and the second represents a belief of how noise is introduced in the actual observed database. To capture this noisy channel model, we introduce the concept of a Probabilistic Unclean Database (PUD), a triple that consists of a probabilistic database that we call the intention, a probabilistic data transformator that we call the realization and captures how noise is introduced, and an observed unclean database that we call the observation. We define three computational problems in the PUD framework: cleaning (infer the most probable intended database, given a PUD), probabilistic query answering (compute the probability of an answer tuple over the unclean observed database), and learning (estimate the most likely intention and realization models of a PUD, given examples as training data). We illustrate the PUD framework on concrete representations of the intention and realization, show that they generalize traditional concepts of repairs such as cardinality and value repairs, draw connections to consistent query answering, and prove tractability results. We further show that parameters can be learned in some practical instantiations, and in fact, prove that under certain conditions we can learn a PUD directly from a single dirty database without any need for clean examples.
Cite as

Christopher De Sa, Ihab F. Ilyas, Benny Kimelfeld, Christopher Ré, and Theodoros Rekatsinas. A Formal Framework for Probabilistic Unclean Databases. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{desa_et_al:LIPIcs.ICDT.2019.6,
  author =	{De Sa, Christopher and Ilyas, Ihab F. and Kimelfeld, Benny and R\'{e}, Christopher and Rekatsinas, Theodoros},
  title =	{{A Formal Framework for Probabilistic Unclean Databases}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.6},
  URN =		{urn:nbn:de:0030-drops-103083},
  doi =		{10.4230/LIPIcs.ICDT.2019.6},
  annote =	{Keywords: Unclean databases, data cleaning, probabilistic databases, noisy channel}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.18
A Single Approach to Decide Chase Termination on Linear Existential Rules

Authors: Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo, and Federico Ulliana

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
Existential rules, long known as tuple-generating dependencies in database theory, have been intensively studied in the last decade as a powerful formalism to represent ontological knowledge in the context of ontology-based query answering. A knowledge base is then composed of an instance that contains incomplete data and a set of existential rules, and answers to queries are logically entailed from the knowledge base. This brought again to light the fundamental chase tool, and its different variants that have been proposed in the literature. It is well-known that the problem of determining, given a chase variant and a set of existential rules, whether the chase will halt on any instance, is undecidable. Hence, a crucial issue is whether it becomes decidable for known subclasses of existential rules. In this work, we consider linear existential rules with atomic head, a simple yet important subclass of existential rules that generalizes inclusion dependencies. We show the decidability of the all-instance chase termination problem on these rules for three main chase variants, namely semi-oblivious, restricted and core chase. To obtain these results, we introduce a novel approach based on so-called derivation trees and a single notion of forbidden pattern. Besides the theoretical interest of a unified approach and new proofs for the semi-oblivious and core chase variants, we provide the first positive decidability results concerning the termination of the restricted chase, proving that chase termination on linear existential rules with atomic head is decidable for both versions of the problem: Does every chase sequence terminate? Does some chase sequence terminate?
Cite as

Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo, and Federico Ulliana. A Single Approach to Decide Chase Termination on Linear Existential Rules. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{leclere_et_al:LIPIcs.ICDT.2019.18,
  author =	{Lecl\`{e}re, Michel and Mugnier, Marie-Laure and Thomazo, Micha\"{e}l and Ulliana, Federico},
  title =	{{A Single Approach to Decide Chase Termination on Linear Existential Rules}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.18},
  URN =		{urn:nbn:de:0030-drops-103200},
  doi =		{10.4230/LIPIcs.ICDT.2019.18},
  annote =	{Keywords: Chase, Tuple Generating Dependencies, Existential rules, Decidability}
}
Document
DOI: 10.4230/DagMan.7.1.96
From Evaluating to Forecasting Performance: How to Turn Information Retrieval, Natural Language Processing and Recommender Systems into Predictive Sciences (Dagstuhl Perspectives Workshop 17442)

Authors: Nicola Ferro, Norbert Fuhr, Gregory Grefenstette, Joseph A. Konstan, Pablo Castells, Elizabeth M. Daly, Thierry Declerck, Michael D. Ekstrand, Werner Geyer, Julio Gonzalo, Tsvi Kuflik, Krister Lindén, Bernardo Magnini, Jian-Yun Nie, Raffaele Perego, Bracha Shapira, Ian Soboroff, Nava Tintarev, Karin Verspoor, Martijn C. Willemsen, and Justin Zobel

Published in: Dagstuhl Manifestos, Volume 7, Issue 1 (2018)

Abstract
We describe the state-of-the-art in performance modeling and prediction for Information Retrieval (IR), Natural Language Processing (NLP) and Recommender Systems (RecSys) along with its shortcomings and strengths. We present a framework for further research, identifying five major problem areas: understanding measures, performance analysis, making underlying assumptions explicit, identifying application features determining performance, and the development of prediction models describing the relationship between assumptions, features and resulting performance.
Cite as

Nicola Ferro, Norbert Fuhr, Gregory Grefenstette, Joseph A. Konstan, Pablo Castells, Elizabeth M. Daly, Thierry Declerck, Michael D. Ekstrand, Werner Geyer, Julio Gonzalo, Tsvi Kuflik, Krister Lindén, Bernardo Magnini, Jian-Yun Nie, Raffaele Perego, Bracha Shapira, Ian Soboroff, Nava Tintarev, Karin Verspoor, Martijn C. Willemsen, and Justin Zobel. From Evaluating to Forecasting Performance: How to Turn Information Retrieval, Natural Language Processing and Recommender Systems into Predictive Sciences (Dagstuhl Perspectives Workshop 17442). In Dagstuhl Manifestos, Volume 7, Issue 1, pp. 96-139, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{ferro_et_al:DagMan.7.1.96,
  author =	{Ferro, Nicola and Fuhr, Norbert and Grefenstette, Gregory and Konstan, Joseph A. and Castells, Pablo and Daly, Elizabeth M. and Declerck, Thierry and Ekstrand, Michael D. and Geyer, Werner and Gonzalo, Julio and Kuflik, Tsvi and Lind\'{e}n, Krister and Magnini, Bernardo and Nie, Jian-Yun and Perego, Raffaele and Shapira, Bracha and Soboroff, Ian and Tintarev, Nava and Verspoor, Karin and Willemsen, Martijn C. and Zobel, Justin},
  title =	{{From Evaluating to Forecasting Performance: How to Turn Information Retrieval, Natural Language Processing and Recommender Systems into Predictive Sciences (Dagstuhl Perspectives Workshop 17442)}},
  pages =	{96--139},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2018},
  volume =	{7},
  number =	{1},
  editor =	{Ferro, Nicola and Fuhr, Norbert and Grefenstette, Gregory and Konstan, Joseph A. and Castells, Pablo and Daly, Elizabeth M. and Declerck, Thierry and Ekstrand, Michael D. and Geyer, Werner and Gonzalo, Julio and Kuflik, Tsvi and Lind\'{e}n, Krister and Magnini, Bernardo and Nie, Jian-Yun and Perego, Raffaele and Shapira, Bracha and Soboroff, Ian and Tintarev, Nava and Verspoor, Karin and Willemsen, Martijn C. and Zobel, Justin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagMan.7.1.96},
  URN =		{urn:nbn:de:0030-drops-98987},
  doi =		{10.4230/DagMan.7.1.96},
  annote =	{Keywords: Information Systems, Formal models, Evaluation, Simulation, User Interaction}
}
Document
DOI: 10.4230/OASIcs.SLATE.2018.13
Evaluation of Distributional Models with the Outlier Detection Task

Authors: Pablo Gamallo

Published in: OASIcs, Volume 62, 7th Symposium on Languages, Applications and Technologies (SLATE 2018)

Abstract
In this article, we define the outlier detection task and use it to compare neural-based word embeddings with transparent count-based distributional representations. Using the English Wikipedia as text source to train the models, we observed that embeddings outperform count-based representations when their contexts are made up of bag-of-words. However, there are no sharp differences between the two models if the word contexts are defined as syntactic dependencies. In general, syntax-based models tend to perform better than those based on bag-of-words for this specific task. Similar experiments were carried out for Portuguese with similar results. The test datasets we have created for outlier detection task in English and Portuguese are released.
Cite as

Pablo Gamallo. Evaluation of Distributional Models with the Outlier Detection Task. In 7th Symposium on Languages, Applications and Technologies (SLATE 2018). Open Access Series in Informatics (OASIcs), Volume 62, pp. 13:1-13:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gamallo:OASIcs.SLATE.2018.13,
  author =	{Gamallo, Pablo},
  title =	{{Evaluation of Distributional Models with the Outlier Detection Task}},
  booktitle =	{7th Symposium on Languages, Applications and Technologies (SLATE 2018)},
  pages =	{13:1--13:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-072-9},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{62},
  editor =	{Henriques, Pedro Rangel and Leal, Jos\'{e} Paulo and Leit\~{a}o, Ant\'{o}nio Menezes and Guinovart, Xavier G\'{o}mez},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2018.13},
  URN =		{urn:nbn:de:0030-drops-92717},
  doi =		{10.4230/OASIcs.SLATE.2018.13},
  annote =	{Keywords: distributional semantics, dependency analysis, outlier detection, similarity}
}
Document
DOI: 10.4230/OASIcs.CMN.2016.11
Annotating Musical Theatre Plots on Narrative Structure and Emotional Content

Authors: Pablo Gervás, Raquel Hervás, Carlos León, and Catherine V. Gale

Published in: OASIcs, Volume 53, 7th Workshop on Computational Models of Narrative (CMN 2016)

Abstract
Although theoretical models of the structure of narrative arising from systematic analysis of corpora are available for domains such as Russian folk tales, there are no such sources for the plot lines of musical theatre. The present paper reports an effort of knowledge elicitation for features that characterise the narrative structure of plot in the particular domain of musical theatre. The following aspects are covered: identification of a valid vocabulary of abstract units to use in annotating musical theatre plots, development of a procedure for annotation - including a spread-sheet format for annotators to use, and a corresponding set of instructions to guide them through the process - selection of a corpus of musical theatre pieces that would constitute the corpus to be annotated, the annotation process itself and the results of post-processing the annotated corpus in search for insights on the narrative structure of musical theatre plots.
Cite as

Pablo Gervás, Raquel Hervás, Carlos León, and Catherine V. Gale. Annotating Musical Theatre Plots on Narrative Structure and Emotional Content. In 7th Workshop on Computational Models of Narrative (CMN 2016). Open Access Series in Informatics (OASIcs), Volume 53, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gervas_et_al:OASIcs.CMN.2016.11,
  author =	{Gerv\'{a}s, Pablo and Herv\'{a}s, Raquel and Le\'{o}n, Carlos and Gale, Catherine V.},
  title =	{{Annotating Musical Theatre Plots on Narrative Structure and Emotional Content}},
  booktitle =	{7th Workshop on Computational Models of Narrative (CMN 2016)},
  pages =	{11:1--11:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-020-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{53},
  editor =	{Miller, Ben and Lieto, Antonio and Ronfard, R\'{e}mi and Ware, Stephen G. and Finlayson, Mark A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2016.11},
  URN =		{urn:nbn:de:0030-drops-67122},
  doi =		{10.4230/OASIcs.CMN.2016.11},
  annote =	{Keywords: Narrative annotation, conceptual representation of narrative, character functions, narrative schemas, musical theatre}
}
  • Refine by Author
  • 4 Gamallo, Pablo
  • 3 Barceló, Pablo
  • 2 Figueira, Diego
  • 2 Gervás, Pablo
  • 2 León, Carlos
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Pattern matching
  • 2 Theory of computation → Randomness, geometry and discrete structures
  • 1 Computing methodologies → Information extraction
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Computing methodologies → Language resources
  • Show More...

  • Refine by Keyword
  • 2 character functions
  • 2 conceptual representation of narrative
  • 2 graph databases
  • 2 narrative schemas
  • 1 Analytic combinatorics
  • Show More...

  • Refine by Type
  • 22 document

  • Refine by Publication Year
  • 4 2019
  • 4 2023
  • 3 2015
  • 2 2009
  • 2 2018
  • Show More...

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