2 Search Results for "Kiel, Stefan"

Document
DOI: 10.4230/LIPIcs.STACS.2021.25
The Edit Distance to k-Subsequence Universality

Authors: Joel D. Day, Pamela Fleischmann, Maria Kosche, Tore Koß, Florin Manea, and Stefan Siemer

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
A word u is a subsequence of another word w if u can be obtained from w by deleting some of its letters. In the early 1970s, Imre Simon defined the relation ∼_k (called now Simon-Congruence) as follows: two words having exactly the same set of subsequences of length at most k are ∼_k-congruent. This relation was central in defining and analysing piecewise testable languages, but has found many applications in areas such as algorithmic learning theory, databases theory, or computational linguistics. Recently, it was shown that testing whether two words are ∼_k-congruent can be done in optimal linear time. Thus, it is a natural next step to ask, for two words w and u which are not ∼_k-equivalent, what is the minimal number of edit operations that we need to perform on w in order to obtain a word which is ∼_k-equivalent to u. In this paper, we consider this problem in a setting which seems interesting: when u is a k-subsequence universal word. A word u with alph(u) = Σ is called k-subsequence universal if the set of subsequences of length k of u contains all possible words of length k over Σ. As such, our results are a series of efficient algorithms computing the edit distance from w to the language of k-subsequence universal words.
Cite as

Joel D. Day, Pamela Fleischmann, Maria Kosche, Tore Koß, Florin Manea, and Stefan Siemer. The Edit Distance to k-Subsequence Universality. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 25:1-25:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{day_et_al:LIPIcs.STACS.2021.25,
  author =	{Day, Joel D. and Fleischmann, Pamela and Kosche, Maria and Ko{\ss}, Tore and Manea, Florin and Siemer, Stefan},
  title =	{{The Edit Distance to k-Subsequence Universality}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.25},
  URN =		{urn:nbn:de:0030-drops-136705},
  doi =		{10.4230/LIPIcs.STACS.2021.25},
  annote =	{Keywords: Subsequence, Scattered factor, Subword, Universality, k-subsequence universality, Edit distance, Efficient algorithms}
}
Document
DOI: 10.4230/DagSemProc.09471.4
Verification and Validation for Femur Prosthesis Surgery

Authors: Ekaterina Auer, Roger Cuypers, Eva Dyllong, Stefan Kiel, and Wolfram Luther

Published in: Dagstuhl Seminar Proceedings, Volume 9471, Computer-assisted proofs - tools, methods and applications (2010)

Abstract
In this paper, we describe how verified methods we are developing in the course of the project TellHim&S (Interval Based Methods For Adaptive Hierarchical Models In Modeling And Simulation Systems) can be applied in the context of the biomechanical project PROREOP (Development of a new prognosis system to optimize patient-specific pre- operative surgical planning for the human skeletal system). On the one hand, it includes the use of verified hierarchical structures for reliable geometric modeling, object decomposition, distance computation and path planning. On the other hand, we cover such tasks as verification and validation assessment and propagation of differently described uncertainties through system models in engineering or mechanics.
Cite as

Ekaterina Auer, Roger Cuypers, Eva Dyllong, Stefan Kiel, and Wolfram Luther. Verification and Validation for Femur Prosthesis Surgery. In Computer-assisted proofs - tools, methods and applications. Dagstuhl Seminar Proceedings, Volume 9471, pp. 1-22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{auer_et_al:DagSemProc.09471.4,
  author =	{Auer, Ekaterina and Cuypers, Roger and Dyllong, Eva and Kiel, Stefan and Luther, Wolfram},
  title =	{{Verification and Validation for Femur Prosthesis Surgery}},
  booktitle =	{Computer-assisted proofs - tools, methods and applications},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9471},
  editor =	{B. Malcolm Brown and Erich Kaltofen and Shin'ichi Oishi and Siegfried M. Rump},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09471.4},
  URN =		{urn:nbn:de:0030-drops-25133},
  doi =		{10.4230/DagSemProc.09471.4},
  annote =	{Keywords: Graphical interface construction, superquadrics, 3D modeling, biomedical engineering}
}
  • Refine by Author
  • 1 Auer, Ekaterina
  • 1 Cuypers, Roger
  • 1 Day, Joel D.
  • 1 Dyllong, Eva
  • 1 Fleischmann, Pamela
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Formal languages and automata theory

  • Refine by Keyword
  • 1 3D modeling
  • 1 Edit distance
  • 1 Efficient algorithms
  • 1 Graphical interface construction
  • 1 Scattered factor
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2010
  • 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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact