7 Search Results for "Muñoz, Martín"

Volume

LIPIcs, Volume 178

27th International Symposium on Temporal Representation and Reasoning (TIME 2020)

TIME 2020, September 23-25, 2020, Bozen-Bolzano, Italy

Editors: Emilio Muñoz-Velasco, Ana Ozaki, and Martin Theobald

Document
DOI: 10.4230/LIPIcs.ICDT.2023.7
Constant-Delay Enumeration for SLP-Compressed Documents

Authors: Martín Muñoz and Cristian Riveros

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

Abstract
We study the problem of enumerating results from a query over a compressed document. The model we use for compression are straight-line programs (SLPs), which are defined by a context-free grammar that produces a single string. For our queries we use a model called Annotated Automata, an extension of regular automata that allows annotations on letters. This model extends the notion of Regular Spanners as it allows arbitrarily long outputs. Our main result is an algorithm which evaluates such a query by enumerating all results with output-linear delay after a preprocessing phase which takes linear time on the size of the SLP, and cubic time over the size of the automaton. This is an improvement over Schmid and Schweikardt’s result [Markus L. Schmid and Nicole Schweikardt, 2021], which, with the same preprocessing time, enumerates with a delay which is logarithmic on the size of the uncompressed document. We achieve this through a persistent data structure named Enumerable Compact Sets with Shifts which guarantees output-linear delay under certain restrictions. These results imply constant-delay enumeration algorithms in the context of regular spanners. Further, we use an extension of annotated automata which utilizes succinctly encoded annotations to save an exponential factor from previous results that dealt with constant-delay enumeration over vset automata. Lastly, we extend our results in the same fashion Schmid and Schweikardt did [Markus L. Schmid and Nicole Schweikardt, 2022] to allow complex document editing while maintaining the constant-delay guarantee.
Cite as

Martín Muñoz and Cristian Riveros. Constant-Delay Enumeration for SLP-Compressed Documents. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{munoz_et_al:LIPIcs.ICDT.2023.7,
  author =	{Mu\~{n}oz, Mart{\'\i}n and Riveros, Cristian},
  title =	{{Constant-Delay Enumeration for SLP-Compressed Documents}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{7:1--7:17},
  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.7},
  URN =		{urn:nbn:de:0030-drops-177495},
  doi =		{10.4230/LIPIcs.ICDT.2023.7},
  annote =	{Keywords: SLP compression, query evaluation, enumeration algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2022.19
Streaming Enumeration on Nested Documents

Authors: Martín Muñoz and Cristian Riveros

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract
Some of the most relevant document schemas used online, such as XML and JSON, have a nested format. In the last decade, the task of extracting data from nested documents over streams has become especially relevant. We focus on the streaming evaluation of queries with outputs of varied sizes over nested documents. We model queries of this kind as Visibly Pushdown Transducers (VPT), a computational model that extends visibly pushdown automata with outputs and has the same expressive power as MSO over nested documents. Since processing a document through a VPT can generate a massive number of results, we are interested in reading the input in a streaming fashion and enumerating the outputs one after another as efficiently as possible, namely, with constant-delay. This paper presents an algorithm that enumerates these elements with constant-delay after processing the document stream in a single pass. Furthermore, we show that this algorithm is worst-case optimal in terms of update-time per symbol and memory usage.
Cite as

Martín Muñoz and Cristian Riveros. Streaming Enumeration on Nested Documents. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{munoz_et_al:LIPIcs.ICDT.2022.19,
  author =	{Mu\~{n}oz, Mart{\'\i}n and Riveros, Cristian},
  title =	{{Streaming Enumeration on Nested Documents}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.19},
  URN =		{urn:nbn:de:0030-drops-158935},
  doi =		{10.4230/LIPIcs.ICDT.2022.19},
  annote =	{Keywords: Streaming, nested documents, query evaluation, enumeration algorithms}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.TIME.2020
LIPIcs, Volume 178, TIME 2020, Complete Volume

Authors: Emilio Muñoz-Velasco, Ana Ozaki, and Martin Theobald

Published in: LIPIcs, Volume 178, 27th International Symposium on Temporal Representation and Reasoning (TIME 2020)

Abstract
LIPIcs, Volume 178, TIME 2020, Complete Volume
Cite as

27th International Symposium on Temporal Representation and Reasoning (TIME 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 178, pp. 1-292, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{munozvelasco_et_al:LIPIcs.TIME.2020,
  title =	{{LIPIcs, Volume 178, TIME 2020, Complete Volume}},
  booktitle =	{27th International Symposium on Temporal Representation and Reasoning (TIME 2020)},
  pages =	{1--292},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-167-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{178},
  editor =	{Mu\~{n}oz-Velasco, Emilio and Ozaki, Ana and Theobald, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2020},
  URN =		{urn:nbn:de:0030-drops-129670},
  doi =		{10.4230/LIPIcs.TIME.2020},
  annote =	{Keywords: LIPIcs, Volume 178, TIME 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.TIME.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Emilio Muñoz-Velasco, Ana Ozaki, and Martin Theobald

Published in: LIPIcs, Volume 178, 27th International Symposium on Temporal Representation and Reasoning (TIME 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

27th International Symposium on Temporal Representation and Reasoning (TIME 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 178, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{munozvelasco_et_al:LIPIcs.TIME.2020.0,
  author =	{Mu\~{n}oz-Velasco, Emilio and Ozaki, Ana and Theobald, Martin},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{27th International Symposium on Temporal Representation and Reasoning (TIME 2020)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-167-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{178},
  editor =	{Mu\~{n}oz-Velasco, Emilio and Ozaki, Ana and Theobald, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2020.0},
  URN =		{urn:nbn:de:0030-drops-129688},
  doi =		{10.4230/LIPIcs.TIME.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.78
Finding Optimal Solutions With Neighborly Help

Authors: Elisabet Burjons, Fabian Frei, Edith Hemaspaandra, Dennis Komm, and David Wehner

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighboring (i.e., locally modified) instances? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems; most notably graph theory’s core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, Colorability and Vertex Cover. For example, we show that it is NP-hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in P. We observe that Vertex Cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for DP (differences of NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For Vertex Cover, we show that recognizing beta-vertex-critical graphs is complete for Theta_2^p (parallel access to NP), obtaining the first completeness result for a criticality problem for this class.
Cite as

Elisabet Burjons, Fabian Frei, Edith Hemaspaandra, Dennis Komm, and David Wehner. Finding Optimal Solutions With Neighborly Help. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{burjons_et_al:LIPIcs.MFCS.2019.78,
  author =	{Burjons, Elisabet and Frei, Fabian and Hemaspaandra, Edith and Komm, Dennis and Wehner, David},
  title =	{{Finding Optimal Solutions With Neighborly Help}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{78:1--78:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.78},
  URN =		{urn:nbn:de:0030-drops-110221},
  doi =		{10.4230/LIPIcs.MFCS.2019.78},
  annote =	{Keywords: Critical Graphs, Computational Complexity, Structural Self-Reducibility, Minimality Problems, Colorability, Vertex Cover, Satisfiability, Reoptimization, Advice}
}
Document
DOI: 10.4230/DFU.Vol6.12191.1
Search in Real-Time Video Games

Authors: Peter I. Cowling, Michael Buro, Michal Bida, Adi Botea, Bruno Bouzy, Martin V. Butz, Philip Hingston, Hector Muñoz-Avila, Dana Nau, and Moshe Sipper

Published in: Dagstuhl Follow-Ups, Volume 6, Artificial and Computational Intelligence in Games (2013)

Abstract
This chapter arises from the discussions of an experienced international group of researchers interested in the potential for creative application of algorithms for searching finite discrete graphs, which have been highly successful in a wide range of application areas, to address a broad range of problems arising in video games. The chapter first summarises the state of the art in search algorithms for games. It then considers the challenges in implementing these algorithms in video games (particularly real time strategy and first-person games) and ways of creating searchable discrete representations of video game decisions (for example as state-action graphs). Finally the chapter looks forward to promising techniques which might bring some of the success achieved in games such as Go and Chess, to real-time video games. For simplicity, we will consider primarily the objective of maximising playing strength, and consider games where this is a challenging task, which results in interesting gameplay.
Cite as

Peter I. Cowling, Michael Buro, Michal Bida, Adi Botea, Bruno Bouzy, Martin V. Butz, Philip Hingston, Hector Muñoz-Avila, Dana Nau, and Moshe Sipper. Search in Real-Time Video Games. In Artificial and Computational Intelligence in Games. Dagstuhl Follow-Ups, Volume 6, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{cowling_et_al:DFU.Vol6.12191.1,
  author =	{Cowling, Peter I. and Buro, Michael and Bida, Michal and Botea, Adi and Bouzy, Bruno and Butz, Martin V. and Hingston, Philip and Mu\~{n}oz-Avila, Hector and Nau, Dana and Sipper, Moshe},
  title =	{{Search in Real-Time Video Games}},
  booktitle =	{Artificial and Computational Intelligence in Games},
  pages =	{1--19},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-62-0},
  ISSN =	{1868-8977},
  year =	{2013},
  volume =	{6},
  editor =	{Lucas, Simon M. and Mateas, Michael and Preuss, Mike and Spronck, Pieter and Togelius, Julian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol6.12191.1},
  URN =		{urn:nbn:de:0030-drops-43328},
  doi =		{10.4230/DFU.Vol6.12191.1},
  annote =	{Keywords: search algorithms, real-time video games, Monte Carlo tree search, minimax search, game theory}
}
  • Refine by Author
  • 2 Muñoz, Martín
  • 2 Muñoz-Velasco, Emilio
  • 2 Ozaki, Ana
  • 2 Riveros, Cristian
  • 2 Theobald, Martin
  • Show More...

  • Refine by Classification
  • 2 Computing methodologies → Knowledge representation and reasoning
  • 2 Information systems → Temporal data
  • 2 Theory of computation → Database theory
  • 2 Theory of computation → Logic
  • 1 Theory of computation → Complexity classes
  • Show More...

  • Refine by Keyword
  • 2 enumeration algorithms
  • 2 query evaluation
  • 1 Advice
  • 1 Colorability
  • 1 Computational Complexity
  • Show More...

  • Refine by Type
  • 6 document
  • 1 volume

  • Refine by Publication Year
  • 3 2020
  • 1 2013
  • 1 2019
  • 1 2022
  • 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