5 Search Results for "Wei�gerber, Peter"


Document
Database Repairing with Soft Functional Dependencies

Authors: Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, and Muhammad Tibi

Published in: LIPIcs, Volume 186, 24th International Conference on Database Theory (ICDT 2021)


Abstract
A common interpretation of soft constraints penalizes the database for every violation of every constraint, where the penalty is the cost (weight) of the constraint. A computational challenge is that of finding an optimal subset: a collection of database tuples that minimizes the total penalty when each tuple has a cost of being excluded. When the constraints are strict (i.e., have an infinite cost), this subset is a "cardinality repair" of an inconsistent database; in soft interpretations, this subset corresponds to a "most probable world" of a probabilistic database, a "most likely intention" of a probabilistic unclean database, and so on. Within the class of functional dependencies, the complexity of finding a cardinality repair is thoroughly understood. Yet, very little is known about the complexity of finding an optimal subset for the more general soft semantics. This paper makes a significant progress in this direction. In addition to general insights about the hardness and approximability of the problem, we present algorithms for two special cases: a single functional dependency, and a bipartite matching. The latter is the problem of finding an optimal "almost matching" of a bipartite graph where a penalty is paid for every lost edge and every violation of monogamy.

Cite as

Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, and Muhammad Tibi. Database Repairing with Soft Functional Dependencies. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{carmeli_et_al:LIPIcs.ICDT.2021.16,
  author =	{Carmeli, Nofar and Grohe, Martin and Kimelfeld, Benny and Livshits, Ester and Tibi, Muhammad},
  title =	{{Database Repairing with Soft Functional Dependencies}},
  booktitle =	{24th International Conference on Database Theory (ICDT 2021)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-179-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{186},
  editor =	{Yi, Ke and Wei, Zhewei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2021.16},
  URN =		{urn:nbn:de:0030-drops-137245},
  doi =		{10.4230/LIPIcs.ICDT.2021.16},
  annote =	{Keywords: Database inconsistency, database repairs, integrity constraints, soft constraints, functional dependencies}
}
Document
Random Subgroups of Rationals

Authors: Ziyuan Gao, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Alexander Melnikov, Karen Seidel, and Frank Stephan

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


Abstract
This paper introduces and studies a notion of algorithmic randomness for subgroups of rationals. Given a randomly generated additive subgroup (G,+) of rationals, two main questions are addressed: first, what are the model-theoretic and recursion-theoretic properties of (G,+); second, what learnability properties can one extract from G and its subclass of finitely generated subgroups? For the first question, it is shown that the theory of (G,+) coincides with that of the additive group of integers and is therefore decidable; furthermore, while the word problem for G with respect to any generating sequence for G is not even semi-decidable, one can build a generating sequence beta such that the word problem for G with respect to beta is co-recursively enumerable (assuming that the set of generators of G is limit-recursive). In regard to the second question, it is proven that there is a generating sequence beta for G such that every non-trivial finitely generated subgroup of G is recursively enumerable and the class of all such subgroups of G is behaviourally correctly learnable, that is, every non-trivial finitely generated subgroup can be semantically identified in the limit (again assuming that the set of generators of G is limit-recursive). On the other hand, the class of non-trivial finitely generated subgroups of G cannot be syntactically identified in the limit with respect to any generating sequence for G. The present work thus contributes to a recent line of research studying algorithmically random infinite structures and uncovers an interesting connection between the arithmetical complexity of the set of generators of a randomly generated subgroup of rationals and the learnability of its finitely generated subgroups.

Cite as

Ziyuan Gao, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Alexander Melnikov, Karen Seidel, and Frank Stephan. Random Subgroups of Rationals. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.MFCS.2019.25,
  author =	{Gao, Ziyuan and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Melnikov, Alexander and Seidel, Karen and Stephan, Frank},
  title =	{{Random Subgroups of Rationals}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{25:1--25: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.25},
  URN =		{urn:nbn:de:0030-drops-109693},
  doi =		{10.4230/LIPIcs.MFCS.2019.25},
  annote =	{Keywords: Martin-L\"{o}f randomness, subgroups of rationals, finitely generated subgroups of rationals, learning in the limit, behaviourally correct learning}
}
Document
The Power Word Problem

Authors: Markus Lohrey and Armin Weiß

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


Abstract
In this work we introduce a new succinct variant of the word problem in a finitely generated group G, which we call the power word problem: the input word may contain powers p^x, where p is a finite word over generators of G and x is a binary encoded integer. The power word problem is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over G). The main result of the paper states that the power word problem for a finitely generated free group F is AC^0-Turing-reducible to the word problem for F. Moreover, the following hardness result is shown: For a wreath product G Wr Z, where G is either free of rank at least two or finite non-solvable, the power word problem is complete for coNP. This contrasts with the situation where G is abelian: then the power word problem is shown to be in TC^0.

Cite as

Markus Lohrey and Armin Weiß. The Power Word Problem. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{lohrey_et_al:LIPIcs.MFCS.2019.43,
  author =	{Lohrey, Markus and Wei{\ss}, Armin},
  title =	{{The Power Word Problem}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{43:1--43:15},
  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.43},
  URN =		{urn:nbn:de:0030-drops-109871},
  doi =		{10.4230/LIPIcs.MFCS.2019.43},
  annote =	{Keywords: word problem, compressed word problem, free groups}
}
Document
The Ideal Storage Cellular Automaton Model

Authors: Andreas Dress, Wim Hordijk, Lin Wei, and Peter Serocka

Published in: Dagstuhl Seminar Proceedings, Volume 10231, Structure Discovery in Biology: Motifs, Networks & Phylogenies (2010)


Abstract
We have implemented and investigated a spatial extension of the orig- inal ideal storage model by embedding it in a 2D cellular automaton with a diffusion-like coupling between neighboring cells. The resulting ideal storage cellular automaton model (ISCAM) generates many interesting spatio-temporal patterns, in particular spiral waves that grow and com- pete" with each other. We study this dynamical behavior both mathemat- ically and computationally, and compare it with similar patterns observed in actual chemical processes. Remarkably, it turned out that one can use such CA for modeling all sorts of complex processes, from phase transition in binary mixtures to using them as a metaphor for cancer onset caused by only one short pulse of 'tissue dis-organzation' (changing e.g. for only one single time step the diffusion coefficient) as hypothesized in recent papers questioning the current gene/genome centric view on cancer onset by AO Ping et al.

Cite as

Andreas Dress, Wim Hordijk, Lin Wei, and Peter Serocka. The Ideal Storage Cellular Automaton Model. In Structure Discovery in Biology: Motifs, Networks & Phylogenies. Dagstuhl Seminar Proceedings, Volume 10231, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{dress_et_al:DagSemProc.10231.8,
  author =	{Dress, Andreas and Hordijk, Wim and Wei, Lin and Serocka, Peter},
  title =	{{The Ideal Storage Cellular Automaton Model}},
  booktitle =	{Structure Discovery in Biology: Motifs, Networks \& Phylogenies},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10231},
  editor =	{Alberto Apostolico and Andreas Dress and Laxmi Parida},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10231.8},
  URN =		{urn:nbn:de:0030-drops-27280},
  doi =		{10.4230/DagSemProc.10231.8},
  annote =	{Keywords: }
}
Document
Subjectivity in Clone Judgment: Can We Ever Agree?

Authors: Cory Kapser, Paul Anderson, Michael Godfrey, Rainer Koschke, Matthias Rieger, Filip van Rysselberghe, and Peter Weißgerber

Published in: Dagstuhl Seminar Proceedings, Volume 6301, Duplication, Redundancy, and Similarity in Software (2007)


Abstract
An objective definition of what a code clone is currently eludes the field. A small study was performed at an international workshop to elicit judgments and discussions from world experts regarding what characteristics define a code clone. Less than half of the clone candidates judged had 80% agreement amongst the judges. Judges appeared to differ primarily in their criteria for judgment rather than their interpretation of the clone candidates. In subsequent open discussion the judges provided several reasons for their judgments. The study casts additional doubt on the reliability of experimental results in the field when the full criterion for clone judgment is not spelled out.

Cite as

Cory Kapser, Paul Anderson, Michael Godfrey, Rainer Koschke, Matthias Rieger, Filip van Rysselberghe, and Peter Weißgerber. Subjectivity in Clone Judgment: Can We Ever Agree?. In Duplication, Redundancy, and Similarity in Software. Dagstuhl Seminar Proceedings, Volume 6301, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{kapser_et_al:DagSemProc.06301.12,
  author =	{Kapser, Cory and Anderson, Paul and Godfrey, Michael and Koschke, Rainer and Rieger, Matthias and van Rysselberghe, Filip and Wei{\ss}gerber, Peter},
  title =	{{Subjectivity in Clone Judgment:  Can We Ever Agree?}},
  booktitle =	{Duplication, Redundancy, and Similarity in Software},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6301},
  editor =	{Rainer Koschke and Ettore Merlo and Andrew Walenstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06301.12},
  URN =		{urn:nbn:de:0030-drops-9701},
  doi =		{10.4230/DagSemProc.06301.12},
  annote =	{Keywords: Code clone, study, inter-rater agreement, ill-defined problem}
}
  • Refine by Author
  • 1 Anderson, Paul
  • 1 Carmeli, Nofar
  • 1 Dress, Andreas
  • 1 Gao, Ziyuan
  • 1 Godfrey, Michael
  • Show More...

  • Refine by Classification
  • 1 Information systems → Data cleaning
  • 1 Theory of computation → Incomplete, inconsistent, and uncertain databases
  • 1 Theory of computation → Inductive inference
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Pseudorandomness and derandomization

  • Refine by Keyword
  • 1 Code clone
  • 1 Database inconsistency
  • 1 Martin-Löf randomness
  • 1 behaviourally correct learning
  • 1 compressed word problem
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2019
  • 1 2007
  • 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