4 Search Results for "Herman, Ivan"

Document
DOI: 10.4230/LIPIcs.ESA.2021.35
Minimum Common String Partition: Exact Algorithms

Authors: Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, and Grigory Reznikov

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
In the minimum common string partition problem (MCSP), one gets two strings and is asked to find the minimum number of cuts in the first string such that the second string can be obtained by rearranging the resulting pieces. It is a difficult algorithmic problem having applications in computational biology, text processing, and data compression. MCSP has been studied extensively from various algorithmic angles: there are many papers studying approximation, heuristic, and parameterized algorithms. At the same time, almost nothing is known about its exact complexity. In this paper, we present new results in this direction. We improve the known 2ⁿ upper bound (where n is the length of input strings) to ϕⁿ where ϕ ≈ 1.618... is the golden ratio. The algorithm uses Fibonacci numbers to encode subsets as monomials of a certain implicit polynomial and extracts one of its coefficients using the fast Fourier transform. Then, we show that the case of constant size alphabet can be solved in subexponential time 2^{O(nlog log n/log n)} by a hybrid strategy: enumerate all long pieces and use dynamic programming over histograms of short pieces. Finally, we prove almost matching lower bounds assuming the Exponential Time Hypothesis.
Cite as

Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, and Grigory Reznikov. Minimum Common String Partition: Exact Algorithms. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cygan_et_al:LIPIcs.ESA.2021.35,
  author =	{Cygan, Marek and Kulikov, Alexander S. and Mihajlin, Ivan and Nikolaev, Maksim and Reznikov, Grigory},
  title =	{{Minimum Common String Partition: Exact Algorithms}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.35},
  URN =		{urn:nbn:de:0030-drops-146167},
  doi =		{10.4230/LIPIcs.ESA.2021.35},
  annote =	{Keywords: similarity measure, string distance, exact algorithms, upper bounds, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2019.15
lambda!-calculus, Intersection Types, and Involutions

Authors: Alberto Ciaffaglione, Pietro Di Gianantonio, Furio Honsell, Marina Lenisa, and Ivan Scagnetto

Published in: LIPIcs, Volume 131, 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)

Abstract
Abramsky’s affine combinatory algebras are models of affine combinatory logic, which refines standard combinatory logic in the direction of Linear Logic. Abramsky introduced various universal models of computation based on affine combinatory algebras, consisting of partial involutions over a suitable formal language {of moves}, in order to discuss reversible computation in a Geometry of Interaction setting. We investigate partial involutions from the point of view of the model theory of lambda!-calculus. The latter is a refinement of the standard lambda-calculus, corresponding to affine combinatory logic. We introduce intersection type systems for the lambda!-calculus, by extending standard intersection types with a !_u-operator. These induce affine combinatory algebras, and, via suitable quotients, models of the lambda!-calculus. In particular, we introduce an intersection type system for assigning principal types to lambda!-terms, and we state a correspondence between the partial involution interpreting a combinator and the principal type of the corresponding lambda!-term. This analogy allows for explaining as unification between principal types the somewhat awkward linear application of involutions arising from Geometry of Interaction.
Cite as

Alberto Ciaffaglione, Pietro Di Gianantonio, Furio Honsell, Marina Lenisa, and Ivan Scagnetto. lambda!-calculus, Intersection Types, and Involutions. In 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 131, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ciaffaglione_et_al:LIPIcs.FSCD.2019.15,
  author =	{Ciaffaglione, Alberto and Di Gianantonio, Pietro and Honsell, Furio and Lenisa, Marina and Scagnetto, Ivan},
  title =	{{lambda!-calculus, Intersection Types, and Involutions}},
  booktitle =	{4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-107-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{131},
  editor =	{Geuvers, Herman},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2019.15},
  URN =		{urn:nbn:de:0030-drops-105228},
  doi =		{10.4230/LIPIcs.FSCD.2019.15},
  annote =	{Keywords: Affine Combinatory Algebra, Affine Lambda-calculus, Intersection Types, Geometry of Interaction}
}
Document
DOI: 10.4230/DagMan.1.1.41
Improving The Future of Research Communications and e-Scholarship (Dagstuhl Perspectives Workshop 11331)

Authors: Philip E. Bourne, Timothy W. Clark, Robert Dale, Anita de Waard, Ivan Herman, Eduard H. Hovy, and David Shotton

Published in: Dagstuhl Manifestos, Volume 1, Issue 1 (2011)

Abstract
The dissemination of knowledge derived from research and scholarship has a fundamental impact on the ways in which society develops and progresses, and at the same time it feeds back to improve subsequent research and scholarship. Here, as in so many other areas of human activity, the internet is changing the way things work; two decades of emergent and increasingly pervasive information technology have demonstrated the potential for far more effective scholarly communication. But the use of this technology remains limited. Force11 is a community of scholars, librarians, archivists, publishers and research funders that has arisen organically to help facilitate the change toward improved knowledge creation and sharing. This document highlights the findings of the Force11 workshop on the Future of Research Communication held at Schloss Dagstuhl, Germany, in August 2011: it summarizes a number of key problems facing scholarly publishing today, and presents a vision that addresses these problems, proposing concrete steps that key stakeholders can take to improve the state of scholarly publishing.
Cite as

Philip E. Bourne, Timothy W. Clark, Robert Dale, Anita de Waard, Ivan Herman, Eduard H. Hovy, and David Shotton. Improving The Future of Research Communications and e-Scholarship (Dagstuhl Perspectives Workshop 11331). In Dagstuhl Manifestos, Volume 1, Issue 1, pp. 41-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{bourne_et_al:DagMan.1.1.41,
  author =	{Bourne, Philip E. and Clark, Timothy W. and Dale, Robert and de Waard, Anita and Herman, Ivan and Hovy, Eduard H. and Shotton, David},
  title =	{{Improving The Future of Research Communications and e-Scholarship (Dagstuhl Perspectives Workshop 11331)}},
  pages =	{41--60},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2012},
  volume =	{1},
  number =	{1},
  editor =	{Bourne, Philip E. and Clark, Timothy W. and Dale, Robert and de Waard, Anita and Herman, Ivan and Hovy, Eduard H. and Shotton, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagMan.1.1.41},
  URN =		{urn:nbn:de:0030-drops-34458},
  doi =		{10.4230/DagMan.1.1.41},
  annote =	{Keywords: Elektronisches Publizieren , Dokumentenserver , Bibliometrie Science publishing, online communities, science policy, digital repositories, semantic publishing, citation analysis}
}
Document
DOI: 10.4230/DagRep.1.8.29
The Future of Research Communication (Dagstuhl Perspectives Workshop 11331)

Authors: Tim Clark, Anita De Waard, Ivan Herman, and Eduard Hovy

Published in: Dagstuhl Reports, Volume 1, Issue 8 (2011)

Abstract
This report documents the program and the outcomes of Dagstuhl Perspectives Workshop 11331 ``The Future of Research Communication''. The purpose of the workshop was to bring together researchers from these different disciplines, whose core research goal is changing the formats, standards, and means by which we communicate science.
Cite as

Tim Clark, Anita De Waard, Ivan Herman, and Eduard Hovy. The Future of Research Communication (Dagstuhl Perspectives Workshop 11331). In Dagstuhl Reports, Volume 1, Issue 8, pp. 29-52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{clark_et_al:DagRep.1.8.29,
  author =	{Clark, Tim and De Waard, Anita and Herman, Ivan and Hovy, Eduard},
  title =	{{The Future of Research Communication (Dagstuhl Perspectives Workshop 11331)}},
  pages =	{29--52},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{8},
  editor =	{Clark, Tim and De Waard, Anita and Herman, Ivan and Hovy, Eduard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.8.29},
  URN =		{urn:nbn:de:0030-drops-33159},
  doi =		{10.4230/DagRep.1.8.29},
  annote =	{Keywords: science publishing, online communities, science policy, new forms of publishing, bioinformatics, digital repositories, semantic publishing, citation analysis, data publication, information access and integration, reporting standards}
}
  • Refine by Author
  • 2 Herman, Ivan
  • 1 Bourne, Philip E.
  • 1 Ciaffaglione, Alberto
  • 1 Clark, Tim
  • 1 Clark, Timothy W.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Algorithm design techniques
  • 1 Theory of computation → Linear logic
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Program semantics

  • Refine by Keyword
  • 2 citation analysis
  • 2 digital repositories
  • 2 online communities
  • 2 science policy
  • 2 semantic publishing
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2011
  • 1 2012
  • 1 2019
  • 1 2021

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