7 Search Results for "Kvarnstr�m, Jonas"

Document
DOI: 10.4230/LIPIcs.ESA.2023.14
Lyndon Arrays in Sublinear Time

Authors: Hideo Bannai and Jonas Ellert

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
A Lyndon word is a string that is lexicographically smaller than all of its non-trivial suffixes. For example, airbus is a Lyndon word, but amtrak is not a Lyndon word due to its suffix ak. The Lyndon array stores the length of the longest Lyndon prefix of each suffix of a string. For a length-n string over a general ordered alphabet, the array can be computed in O(n) time (Bille et al., ICALP 2020). However, on a word-RAM of word-width w ≥ log₂ n, linear time is not optimal if the string is over integer alphabet {0, … , σ} with σ ≪ n. In this case, the string can be stored in O(n log σ) bits (or O(n / log_σ n) words) of memory, and reading it takes only O(n / log_σ n) time. We show that O(n / log_σ n) time and words of space suffice to compute the succinct 2n-bit version of the Lyndon array. The time is optimal for w = O(log n). The algorithm uses precomputed lookup tables to perform significant parts of the computation in constant time. This is possible due to properties of periodic substrings, which we carefully analyze to achieve the desired result. We envision that the algorithm has applications in the computation of runs (maximal periodic substrings), where the Lyndon array plays a central role in both theoretically and practically fast algorithms.
Cite as

Hideo Bannai and Jonas Ellert. Lyndon Arrays in Sublinear Time. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bannai_et_al:LIPIcs.ESA.2023.14,
  author =	{Bannai, Hideo and Ellert, Jonas},
  title =	{{Lyndon Arrays in Sublinear Time}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.14},
  URN =		{urn:nbn:de:0030-drops-186670},
  doi =		{10.4230/LIPIcs.ESA.2023.14},
  annote =	{Keywords: Lyndon forest, Lyndon table, Lyndon array, sublinear time algorithms, word RAM algorithms, word packing, tabulation, lookup tables, periodicity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CPM.2021.1
Repetitions in Strings: A "Constant" Problem (Invited Talk)

Authors: Hideo Bannai

Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)

Abstract
Repeating structures in strings is one of the most fundamental characteristics of strings, and has been an important topic in the field of combinatorics on words and combinatorial pattern matching since their beginnings. In this talk, I will focus on squares and maximal repetitions and review the "runs" theorem [Hideo Bannai et al., 2017] as well as related results (e.g. [Aviezri S. Fraenkel and Jamie Simpson, 1998; Yuta Fujishige et al., 2017; Ryo Sugahara et al., 2019; Philip Bille et al., 2020; Hideo Bannai et al., 2020; Jonas Ellert and Johannes Fischer, 2021]) which address the two main questions: how many of them can be contained in a string of given length, and algorithms for computing them.
Cite as

Hideo Bannai. Repetitions in Strings: A "Constant" Problem (Invited Talk). In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bannai:LIPIcs.CPM.2021.1,
  author =	{Bannai, Hideo},
  title =	{{Repetitions in Strings: A "Constant" Problem}},
  booktitle =	{32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-186-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{191},
  editor =	{Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.1},
  URN =		{urn:nbn:de:0030-drops-139523},
  doi =		{10.4230/LIPIcs.CPM.2021.1},
  annote =	{Keywords: Maximal repetitions, Squares, Lyndon words}
}
Document
DOI: 10.4230/OASIcs.iPMVM.2020.19
Interpolation of Scientific Image Databases

Authors: Eric Georg Kinner, Jonas Lukasczyk, David Honegger Rogers, Ross Maciejewski, and Christoph Garth

Published in: OASIcs, Volume 89, 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)

Abstract
This paper explores how recent convolutional neural network (CNN)-based techniques can be used to interpolate images inside scientific image databases. These databases are frequently used for the interactive visualization of large-scale simulations, where images correspond to samples of the parameter space (e.g., timesteps, isovalues, thresholds, etc.) and the visualization space (e.g., camera locations, clipping planes, etc.). These databases can be browsed post hoc along the sampling axis to emulate real-time interaction with large-scale datasets. However, the resulting databases are limited to their contained images, i.e., the sampling points. In this paper, we explore how efficiently and accurately CNN-based techniques can derive new images by interpolating database elements. We demonstrate on several real-world examples that the size of databases can be further reduced by dropping samples that can be interpolated post hoc with an acceptable error, which we measure qualitatively and quantitatively.
Cite as

Eric Georg Kinner, Jonas Lukasczyk, David Honegger Rogers, Ross Maciejewski, and Christoph Garth. Interpolation of Scientific Image Databases. In 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020). Open Access Series in Informatics (OASIcs), Volume 89, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kinner_et_al:OASIcs.iPMVM.2020.19,
  author =	{Kinner, Eric Georg and Lukasczyk, Jonas and Rogers, David Honegger and Maciejewski, Ross and Garth, Christoph},
  title =	{{Interpolation of Scientific Image Databases}},
  booktitle =	{2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)},
  pages =	{19:1--19:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-183-2},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{89},
  editor =	{Garth, Christoph and Aurich, Jan C. and Linke, Barbara and M\"{u}ller, Ralf and Ravani, Bahram and Weber, Gunther H. and Kirsch, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.iPMVM.2020.19},
  URN =		{urn:nbn:de:0030-drops-137686},
  doi =		{10.4230/OASIcs.iPMVM.2020.19},
  annote =	{Keywords: Image Interpolation, Image Database, Cinema Database}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSCD.2020.4
Certifying the Weighted Path Order (Invited Talk)

Authors: René Thiemann, Jonas Schöpf, Christian Sternagel, and Akihisa Yamada

Published in: LIPIcs, Volume 167, 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)

Abstract
The weighted path order (WPO) unifies and extends several termination proving techniques that are known in term rewriting. Consequently, the first tool implementing WPO could prove termination of rewrite systems for which all previous tools failed. However, we should not blindly trust such results, since there might be problems with the implementation or the paper proof of WPO. In this work, we increase the reliability of these automatically generated proofs. To this end, we first formally prove the properties of WPO in Isabelle/HOL, and then develop a verified algorithm to certify termination proofs that are generated by tools using WPO. We also include support for max-polynomial interpretations, an important ingredient in WPO. Here we establish a connection to an existing verified SMT solver. Moreover, we extend the termination tools NaTT and TTT2, so that they can now generate certifiable WPO proofs.
Cite as

René Thiemann, Jonas Schöpf, Christian Sternagel, and Akihisa Yamada. Certifying the Weighted Path Order (Invited Talk). In 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 167, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{thiemann_et_al:LIPIcs.FSCD.2020.4,
  author =	{Thiemann, Ren\'{e} and Sch\"{o}pf, Jonas and Sternagel, Christian and Yamada, Akihisa},
  title =	{{Certifying the Weighted Path Order}},
  booktitle =	{5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-155-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{167},
  editor =	{Ariola, Zena M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2020.4},
  URN =		{urn:nbn:de:0030-drops-123263},
  doi =		{10.4230/LIPIcs.FSCD.2020.4},
  annote =	{Keywords: certification, Isabelle/HOL, reduction order, termination analysis}
}
Document
DOI: 10.4230/DagSemProc.10081.13
Research with Collaborative Unmanned Aircraft Systems

Authors: Patrick Doherty, Jonas Kvarnström, Fredrik Heintz, D. Landen, and P.-M. Olsson

Published in: Dagstuhl Seminar Proceedings, Volume 10081, Cognitive Robotics (2010)

Abstract
We provide an overview of ongoing research which targets development of a principled framework for mixed-initiative interaction with unmanned aircraft systems (UAS). UASs are now becoming technologically mature enough to be integrated into civil society. Principled interaction between UASs and human resources is an essential component in their future uses in complex emergency services or bluelight scenarios. In our current research, we have targeted a triad of fundamental, interdependent conceptual issues: delegation, mixed- initiative interaction and adjustable autonomy, that is being used as a basis for developing a principled and well-defined framework for interaction. This can be used to clarify, validate and verify different types of interaction between human operators and UAS systems both theoretically and practically in UAS experimentation with our deployed platforms.
Cite as

Patrick Doherty, Jonas Kvarnström, Fredrik Heintz, D. Landen, and P.-M. Olsson. Research with Collaborative Unmanned Aircraft Systems. In Cognitive Robotics. Dagstuhl Seminar Proceedings, Volume 10081, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{doherty_et_al:DagSemProc.10081.13,
  author =	{Doherty, Patrick and Kvarnstr\"{o}m, Jonas and Heintz, Fredrik and Landen, D. and Olsson, P.-M.},
  title =	{{Research with Collaborative Unmanned Aircraft Systems}},
  booktitle =	{Cognitive Robotics},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10081},
  editor =	{Gerhard Lakemeyer and Hector J. Levesque and Fiora Pirri},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10081.13},
  URN =		{urn:nbn:de:0030-drops-26300},
  doi =		{10.4230/DagSemProc.10081.13},
  annote =	{Keywords: Multi-agent systems, robotics, human-robot interaction, delegation}
}
Document
DOI: 10.4230/DagSemProc.10081.16
Stream-Based Reasoning in DyKnow

Authors: Fredrik Heintz, Jonas Kvarnström, and Patrick Doherty

Published in: Dagstuhl Seminar Proceedings, Volume 10081, Cognitive Robotics (2010)

Abstract
The information available to modern autonomous systems is often in the form of streams. As the number of sensors and other stream sources increases there is a growing need for incremental reasoning about the incomplete content of sets of streams in order to draw relevant conclusions and react to new situations as quickly as possible. To act rationally, autonomous agents often depend on high level reasoning components that require crisp, symbolic knowledge about the environment. Extensive processing at many levels of abstraction is required to generate such knowledge from noisy, incomplete and quantitative sensor data. We define knowledge processing middleware as a systematic approach to integrating and organizing such processing, and argue that connecting processing components with streams provides essential support for steady and timely flows of information. DyKnow is a concrete and implemented instantiation of such middleware, providing support for stream reasoning at several levels. First, the formal kpl language allows the specification of streams connecting knowledge processes and the required properties of such streams. Second, chronicle recognition incrementally detects complex events from streams of more primitive events. Third, complex metric temporal formulas can be incrementally evaluated over streams of states. DyKnow and the stream reasoning techniques are described and motivated in the context of a UAV traffic monitoring application.
Cite as

Fredrik Heintz, Jonas Kvarnström, and Patrick Doherty. Stream-Based Reasoning in DyKnow. In Cognitive Robotics. Dagstuhl Seminar Proceedings, Volume 10081, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{heintz_et_al:DagSemProc.10081.16,
  author =	{Heintz, Fredrik and Kvarnstr\"{o}m, Jonas and Doherty, Patrick},
  title =	{{Stream-Based Reasoning in DyKnow}},
  booktitle =	{Cognitive Robotics},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10081},
  editor =	{Gerhard Lakemeyer and Hector J. Levesque and Fiora Pirri},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10081.16},
  URN =		{urn:nbn:de:0030-drops-26274},
  doi =		{10.4230/DagSemProc.10081.16},
  annote =	{Keywords: Knowledge representation, autonomous systems, stream-based reasoning}
}
Document
DOI: 10.4230/DagSemProc.08441.2
08441 Final Report – Emerging Uses and Paradigms for Dynamic Binary Translation

Authors: Erik Altman, Bruce R. Childers, Robert Cohn, Jack Davidson, Koen De Brosschere, Bjorn De Sutter, Anton M. Ertl, Michael Franz, Yuan Gu, Matthias Hauswirth, Thomas Heinz, Wei-Chung Hsu, Jens Knoop, Andreas Krall, Naveen Kumar, Jonas Maebe, Robert Muth, Xavier Rival, Erven Rohou, Roni Rosner, Mary Lou Soffa, Jens Troeger, and Christopher Vick

Published in: Dagstuhl Seminar Proceedings, Volume 8441, Emerging Uses and Paradigms for Dynamic Binary Translation (2009)

Abstract
Software designers and developers face many problems in designing, building, deploying, and maintaining cutting-edge software applications–reliability,security,performance,power,legacy code,use of multi-core platforms,and maintenance are just a few of the issues that must be considered. Many of these issues are fundamental parts of the grand challenges in computer science such as reliability and security.
Cite as

Erik Altman, Bruce R. Childers, Robert Cohn, Jack Davidson, Koen De Brosschere, Bjorn De Sutter, Anton M. Ertl, Michael Franz, Yuan Gu, Matthias Hauswirth, Thomas Heinz, Wei-Chung Hsu, Jens Knoop, Andreas Krall, Naveen Kumar, Jonas Maebe, Robert Muth, Xavier Rival, Erven Rohou, Roni Rosner, Mary Lou Soffa, Jens Troeger, and Christopher Vick. 08441 Final Report – Emerging Uses and Paradigms for Dynamic Binary Translation. In Emerging Uses and Paradigms for Dynamic Binary Translation. Dagstuhl Seminar Proceedings, Volume 8441, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{altman_et_al:DagSemProc.08441.2,
  author =	{Altman, Erik and Childers, Bruce R. and Cohn, Robert and Davidson, Jack and De Brosschere, Koen and De Sutter, Bjorn and Ertl, Anton M. and Franz, Michael and Gu, Yuan and Hauswirth, Matthias and Heinz, Thomas and Hsu, Wei-Chung and Knoop, Jens and Krall, Andreas and Kumar, Naveen and Maebe, Jonas and Muth, Robert and Rival, Xavier and Rohou, Erven and Rosner, Roni and Soffa, Mary Lou and Troeger, Jens and Vick, Christopher},
  title =	{{08441 Final Report – Emerging Uses and Paradigms for Dynamic Binary Translation}},
  booktitle =	{Emerging Uses and Paradigms for Dynamic Binary Translation},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8441},
  editor =	{Bruce R. Childers and Jack Davidson and Koen De Bosschere and Mary Lou Soffa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08441.2},
  URN =		{urn:nbn:de:0030-drops-18888},
  doi =		{10.4230/DagSemProc.08441.2},
  annote =	{Keywords: Dynamic binary translation, Virtual machines}
}
  • Refine by Author
  • 2 Bannai, Hideo
  • 2 Doherty, Patrick
  • 2 Heintz, Fredrik
  • 2 Kvarnström, Jonas
  • 1 Altman, Erik
  • Show More...

  • Refine by Classification
  • 1 Computing methodologies → Image processing
  • 1 Mathematics of computing → Combinatorics on words
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Equational logic and rewriting
  • 1 Theory of computation → Logic and verification

  • Refine by Keyword
  • 1 Cinema Database
  • 1 Dynamic binary translation
  • 1 Image Database
  • 1 Image Interpolation
  • 1 Isabelle/HOL
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2010
  • 2 2021
  • 1 2009
  • 1 2020
  • 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