15 Search Results for "May, Wolfgang"


Document
No-Dimensional Tverberg Theorems and Algorithms

Authors: Aruni Choudhary and Wolfgang Mulzer

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)


Abstract
Tverberg’s theorem states that for any k ≥ 2 and any set P ⊂ ℝ^d of at least (d + 1)(k - 1) + 1 points, we can partition P into k subsets whose convex hulls have a non-empty intersection. The associated search problem lies in the complexity class PPAD ∩ PLS, but no hardness results are known. In the colorful Tverberg theorem, the points in P have colors, and under certain conditions, P can be partitioned into colorful sets, in which each color appears exactly once and whose convex hulls intersect. To date, the complexity of the associated search problem is unresolved. Recently, Adiprasito, Bárány, and Mustafa [SODA 2019] gave a no-dimensional Tverberg theorem, in which the convex hulls may intersect in an approximate fashion. This relaxes the requirement on the cardinality of P. The argument is constructive, but does not result in a polynomial-time algorithm. We present a deterministic algorithm that finds for any n-point set P ⊂ ℝ^d and any k ∈ {2, … , n} in O(nd ⌈log k⌉) time a k-partition of P such that there is a ball of radius O((k/√n)diam(P)) that intersects the convex hull of each set. Given that this problem is not known to be solvable exactly in polynomial time, and that there are no approximation algorithms that are truly polynomial in any dimension, our result provides a remarkably efficient and simple new notion of approximation. Our main contribution is to generalize Sarkaria’s method [Israel Journal Math., 1992] to reduce the Tverberg problem to the Colorful Carathéodory problem (in the simplified tensor product interpretation of Bárány and Onn) and to apply it algorithmically. It turns out that this not only leads to an alternative algorithmic proof of a no-dimensional Tverberg theorem, but it also generalizes to other settings such as the colorful variant of the problem.

Cite as

Aruni Choudhary and Wolfgang Mulzer. No-Dimensional Tverberg Theorems and Algorithms. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.SoCG.2020.31,
  author =	{Choudhary, Aruni and Mulzer, Wolfgang},
  title =	{{No-Dimensional Tverberg Theorems and Algorithms}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.31},
  URN =		{urn:nbn:de:0030-drops-121893},
  doi =		{10.4230/LIPIcs.SoCG.2020.31},
  annote =	{Keywords: Tverberg’s theorem, Colorful Carath\'{e}odory Theorem, Tensor lifting}
}
Document
Triangles and Girth in Disk Graphs and Transmission Graphs

Authors: Haim Kaplan, Katharina Klost, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
Let S subset R^2 be a set of n sites, where each s in S has an associated radius r_s > 0. The disk graph D(S) is the undirected graph with vertex set S and an undirected edge between two sites s, t in S if and only if |st| <= r_s + r_t, i.e., if the disks with centers s and t and respective radii r_s and r_t intersect. Disk graphs are used to model sensor networks. Similarly, the transmission graph T(S) is the directed graph with vertex set S and a directed edge from a site s to a site t if and only if |st| <= r_s, i.e., if t lies in the disk with center s and radius r_s. We provide algorithms for detecting (directed) triangles and, more generally, computing the length of a shortest cycle (the girth) in D(S) and in T(S). These problems are notoriously hard in general, but better solutions exist for special graph classes such as planar graphs. We obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that a shortest (Euclidean) triangle in D(S) and in T(S) can be found in O(n log n) expected time, and that the (weighted) girth of D(S) can be found in O(n log n) expected time. For this, we develop new tools for batched range searching that may be of independent interest.

Cite as

Haim Kaplan, Katharina Klost, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Triangles and Girth in Disk Graphs and Transmission Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.ESA.2019.64,
  author =	{Kaplan, Haim and Klost, Katharina and Mulzer, Wolfgang and Roditty, Liam and Seiferth, Paul and Sharir, Micha},
  title =	{{Triangles and Girth in Disk Graphs and Transmission Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{64:1--64:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.64},
  URN =		{urn:nbn:de:0030-drops-111859},
  doi =		{10.4230/LIPIcs.ESA.2019.64},
  annote =	{Keywords: disk graph, transmission graph, triangle, girth}
}
Document
Static Typing of Complex Presence Constraints in Interfaces

Authors: Nathalie Oostvogels, Joeri De Koster, and Wolfgang De Meuter

Published in: LIPIcs, Volume 109, 32nd European Conference on Object-Oriented Programming (ECOOP 2018)


Abstract
Many functions in libraries and APIs have the notion of optional parameters, which can be mapped onto optional properties of an object representing those parameters. The fact that properties are optional opens up the possibility for APIs and libraries to design a complex "dependency logic" between properties: for example, some properties may be mutually exclusive, some properties may depend on others, etc. Existing type systems are not strong enough to express such dependency logic, which can lead to the creation of invalid objects and accidental usage of absent properties. In this paper we propose TypeScriptIPC: a variant of TypeScript with a novel type system that enables programmers to express complex presence constraints on properties. We prove that it is sound with respect to enforcing complex dependency logic defined by the programmer when an object is created, modified or accessed.

Cite as

Nathalie Oostvogels, Joeri De Koster, and Wolfgang De Meuter. Static Typing of Complex Presence Constraints in Interfaces. In 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 109, pp. 14:1-14:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{oostvogels_et_al:LIPIcs.ECOOP.2018.14,
  author =	{Oostvogels, Nathalie and De Koster, Joeri and De Meuter, Wolfgang},
  title =	{{Static Typing of Complex Presence Constraints in Interfaces}},
  booktitle =	{32nd European Conference on Object-Oriented Programming (ECOOP 2018)},
  pages =	{14:1--14:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-079-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{109},
  editor =	{Millstein, Todd},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2018.14},
  URN =		{urn:nbn:de:0030-drops-92196},
  doi =		{10.4230/LIPIcs.ECOOP.2018.14},
  annote =	{Keywords: type checking, interfaces, dependency logic}
}
Document
Static Typing of Complex Presence Constraints in Interfaces (Artifact)

Authors: Nathalie Oostvogels, Joeri De Koster, and Wolfgang De Meuter

Published in: DARTS, Volume 4, Issue 3, Special Issue of the 32nd European Conference on Object-Oriented Programming (ECOOP 2018)


Abstract
This artifact is based on TypeScriptIPC, a statically typed programming language with interfaces in which complex presence constraints can be defined. This enables developers to express inter-property constraints on interface properties. The need for these inter-property constraints stems from web APIs, which often impose a complex "dependency logic" between properties. For example, some properties may be mutually exclusive, or the presence of a property may depend on the presence of others, etc. TypeScriptIPC is a variant of TypeScript, in which interfaces are extended to express constraints over multiple properties, using propositional logic. This artifact contains documentation on how to build and run TypeScriptIPC, such that the code snippets from the paper can be run.

Cite as

Nathalie Oostvogels, Joeri De Koster, and Wolfgang De Meuter. Static Typing of Complex Presence Constraints in Interfaces (Artifact). In Special Issue of the 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Dagstuhl Artifacts Series (DARTS), Volume 4, Issue 3, pp. 3:1-3:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@Article{oostvogels_et_al:DARTS.4.3.3,
  author =	{Oostvogels, Nathalie and De Koster, Joeri and De Meuter, Wolfgang},
  title =	{{Static Typing of Complex Presence Constraints in Interfaces (Artifact)}},
  pages =	{3:1--3:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2018},
  volume =	{4},
  number =	{3},
  editor =	{Oostvogels, Nathalie and De Koster, Joeri and De Meuter, Wolfgang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.4.3.3},
  URN =		{urn:nbn:de:0030-drops-92422},
  doi =		{10.4230/DARTS.4.3.3},
  annote =	{Keywords: type system, interfaces, dependency logic}
}
Document
Routing in Polygonal Domains

Authors: Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber, and Max Willert

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)


Abstract
We consider the problem of routing a data packet through the visibility graph of a polygonal domain P with n vertices and h holes. We may preprocess P to obtain a label and a routing table for each vertex. Then, we must be able to route a data packet between any two vertices p and q of P , where each step must use only the label of the target node q and the routing table of the current node. For any fixed eps > 0, we pre ent a routing scheme that always achieves a routing path that exceeds the shortest path by a factor of at most 1 + eps. The labels have O(log n) bits, and the routing tables are of size O((eps^{-1} + h) log n). The preprocessing time is O(n^2 log n + hn^2 + eps^{-1}hn). It can be improved to O(n 2 + eps^{-1}n) for simple polygons.

Cite as

Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber, and Max Willert. Routing in Polygonal Domains. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{banyassady_et_al:LIPIcs.ISAAC.2017.10,
  author =	{Banyassady, Bahareh and Chiu, Man-Kwun and Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'{e} and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik and Vogtenhuber, Birgit and Willert, Max},
  title =	{{Routing in Polygonal Domains}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.10},
  URN =		{urn:nbn:de:0030-drops-82379},
  doi =		{10.4230/LIPIcs.ISAAC.2017.10},
  annote =	{Keywords: polygonal domains, routing scheme, small stretch,Yao graph}
}
Document
Improved Time-Space Trade-Offs for Computing Voronoi Diagrams

Authors: Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)


Abstract
Let P be a planar n-point set in general position. For k between 1 and n-1, the Voronoi diagram of order k is obtained by subdividing the plane into regions such that points in the same cell have the same set of nearest k neighbors in P. The (nearest point) Voronoi diagram (NVD) and the farthest point Voronoi diagram (FVD) are the particular cases of k=1 and k=n-1, respectively. It is known that the family of all higher-order Voronoi diagrams of order 1 to K for P can be computed in total time O(n K^2 + n log n) using O(K^2(n-K)) space. Also NVD and FVD can be computed in O(n log n) time using O(n) space. For s in {1, ..., n}, an s-workspace algorithm has random access to a read-only array with the sites of P in arbitrary order. Additionally, the algorithm may use O(s) words of Theta(log n) bits each for reading and writing intermediate data. The output can be written only once and cannot be accessed afterwards. We describe a deterministic s-workspace algorithm for computing an NVD and also an FVD for P that runs in O((n^2/s) log s) time. Moreover, we generalize our s-workspace algorithm for computing the family of all higher-order Voronoi diagrams of P up to order K in O(sqrt(s)) in total time O( (n^2 K^6 / s) log^(1+epsilon)(K) (log s / log K)^(O(1)) ) for any fixed epsilon > 0. Previously, for Voronoi diagrams, the only known s-workspace algorithm was to find an NVD for P in expected time O((n^2/s) log s + n log s log^*s). Unlike the previous algorithm, our new method is very simple and does not rely on advanced data structures or random sampling techniques.

Cite as

Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein. Improved Time-Space Trade-Offs for Computing Voronoi Diagrams. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{banyassady_et_al:LIPIcs.STACS.2017.9,
  author =	{Banyassady, Bahareh and Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'{e} and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik},
  title =	{{Improved Time-Space Trade-Offs for Computing Voronoi Diagrams}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.9},
  URN =		{urn:nbn:de:0030-drops-70249},
  doi =		{10.4230/LIPIcs.STACS.2017.9},
  annote =	{Keywords: memory-constrained model, Voronoi diagram, time-space trade-off}
}
Document
Approximability of the Discrete Fréchet Distance

Authors: Karl Bringmann and Wolfgang Mulzer

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)


Abstract
The Fréchet distance is a popular and widespread distance measure for point sequences and for curves. About two years ago, Agarwal et al [SIAM J. Comput. 2014] presented a new (mildly) subquadratic algorithm for the discrete version of the problem. This spawned a flurry of activity that has led to several new algorithms and lower bounds. In this paper, we study the approximability of the discrete Fréchet distance. Building on a recent result by Bringmann [FOCS 2014], we present a new conditional lower bound that strongly subquadratic algorithms for the discrete Fréchet distance are unlikely to exist, even in the one-dimensional case and even if the solution may be approximated up to a factor of 1.399. This raises the question of how well we can approximate the Fréchet distance (of two given d-dimensional point sequences of length n) in strongly subquadratic time. Previously, no general results were known. We present the first such algorithm by analysing the approximation ratio of a simple, linear-time greedy algorithm to be 2^Theta(n). Moreover, we design an alpha-approximation algorithm that runs in time O(n log n + n^2 / alpha), for any alpha in [1, n]. Hence, an n^epsilon-approximation of the Fréchet distance can be computed in strongly subquadratic time, for any epsilon > 0.

Cite as

Karl Bringmann and Wolfgang Mulzer. Approximability of the Discrete Fréchet Distance. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 739-753, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.SOCG.2015.739,
  author =	{Bringmann, Karl and Mulzer, Wolfgang},
  title =	{{Approximability of the Discrete Fr\'{e}chet Distance}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{739--753},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.739},
  URN =		{urn:nbn:de:0030-drops-51072},
  doi =		{10.4230/LIPIcs.SOCG.2015.739},
  annote =	{Keywords: Fr\'{e}chet distance, approximation, lower bounds, Strong Exponential Time Hypothesis}
}
Document
Separations of Non-monotonic Randomness Notions

Authors: Laurent Bienvenu, Rupert Hölzl, Thorsten Kräling, and Wolfgang Merkle

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)


Abstract
In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received most attention are perhaps Martin-L\"of randomness and computable randomness. The latter notion was introduced by Schnorr and is rather natural: an infinite binary sequence is computably random if no total computable strategy succeeds on it by betting on bits in order. However, computably random sequences can have properties that one may consider to be incompatible with being random, in particular, there are computably random sequences that are highly compressible. The concept of Martin-L\"of randomness is much better behaved in this and other respects, on the other hand its definition in terms of martingales is considerably less natural. Muchnik, elaborating on ideas of Kolmogorov and Loveland, refined Schnorr's model by also allowing non-monotonic strategies, i.e.\ strategies that do not bet on bits in order. The subsequent ``non-monotonic'' notion of randomness, now called Kolmogorov-Loveland-randomness, has been shown to be quite close to Martin-L\"of randomness, but whether these two classes coincide remains a fundamental open question. In order to get a better understanding of non-monotonic randomness notions, Miller and Nies introduced some interesting intermediate concepts, where one only allows non-adaptive strategies, i.e., strategies that can still bet non-monotonically, but such that the sequence of betting positions is known in advance (and computable). Recently, these notions were shown by Kastermans and Lempp to differ from Martin-L\"of randomness. We continue the study of the non-monotonic randomness notions introduced by Miller and Nies and obtain results about the Kolmogorov complexities of initial segments that may and may not occur for such sequences, where these results then imply a complete classification of these randomness notions by order of strength.

Cite as

Laurent Bienvenu, Rupert Hölzl, Thorsten Kräling, and Wolfgang Merkle. Separations of Non-monotonic Randomness Notions. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:OASIcs.CCA.2009.2260,
  author =	{Bienvenu, Laurent and H\"{o}lzl, Rupert and Kr\"{a}ling, Thorsten and Merkle, Wolfgang},
  title =	{{Separations of Non-monotonic Randomness Notions}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{71--82},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2260},
  URN =		{urn:nbn:de:0030-drops-22601},
  doi =		{10.4230/OASIcs.CCA.2009.2260},
  annote =	{Keywords: Martin-L\"{o}f randomness, Kolmogorov-Loveland randomness, Kolmogorov complexity, martingales, betting strategies}
}
Document
Declarative Synchronous Multithreaded Programming

Authors: Blanca Mancilla and John Plaice

Published in: Dagstuhl Seminar Proceedings, Volume 8271, Topological and Game-Theoretic Aspects of Infinite Computations (2008)


Abstract
We demonstrate how TransLucid can be used as a reactive system. At each instant, there is a set of active ports, where sets of equations, demands and threads are all registered. Each thread defines a sequence of (state, demand) pairs, and threads may interact through the overall set of equations. The entire system remains fully declarative.

Cite as

Blanca Mancilla and John Plaice. Declarative Synchronous Multithreaded Programming. In Topological and Game-Theoretic Aspects of Infinite Computations. Dagstuhl Seminar Proceedings, Volume 8271, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{mancilla_et_al:DagSemProc.08271.4,
  author =	{Mancilla, Blanca and Plaice, John},
  title =	{{Declarative Synchronous Multithreaded Programming}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08271.4},
  URN =		{urn:nbn:de:0030-drops-16536},
  doi =		{10.4230/DagSemProc.08271.4},
  annote =	{Keywords: Synchronous programming, distributed computing, declarative programming, Cartesian programming, multidimensional programming.}
}
Document
Ambient Assisted Living Systems - The Conflicts between Technology, Acceptance, Ethics and Privacy

Authors: Wolfgang L. Zagler, Paul Panek, and Marjo Rauhala

Published in: Dagstuhl Seminar Proceedings, Volume 7462, Assisted Living Systems - Models, Architectures and Engineering Approaches (2008)


Abstract
Installing and using AAL Smart Home-systems in the homes of older people not only offers a tremendous potential for increasing safety and quality of life but may also evoke reluctance and anxiety. Will such a system become a "Big Brother" watching the steps and the behaviour of the inhabitants and betray them to their outside world? In several field-trials of an AAL Smart Home-system with inhabitants of senior residences we were able to learn about the issues concerning acceptance, ethics and privacy when senior citizens and their care persons are confronted with this kind of technology for the first time.

Cite as

Wolfgang L. Zagler, Paul Panek, and Marjo Rauhala. Ambient Assisted Living Systems - The Conflicts between Technology, Acceptance, Ethics and Privacy. In Assisted Living Systems - Models, Architectures and Engineering Approaches. Dagstuhl Seminar Proceedings, Volume 7462, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{zagler_et_al:DagSemProc.07462.5,
  author =	{Zagler, Wolfgang L. and Panek, Paul and Rauhala, Marjo},
  title =	{{Ambient Assisted Living Systems - The Conflicts between Technology, Acceptance, Ethics and Privacy}},
  booktitle =	{Assisted Living Systems - Models, Architectures and Engineering Approaches},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7462},
  editor =	{Arthur I. Karshmer and J\"{u}rgen Nehmer and Hartmut Raffler and Gerhard Tr\"{o}ster},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07462.5},
  URN =		{urn:nbn:de:0030-drops-14549},
  doi =		{10.4230/DagSemProc.07462.5},
  annote =	{Keywords: AAL, Ambient Assisted Living, Smart Homes, field trials, acceptance, ethics, privacy protection, data protection}
}
Document
The Grand Challenges and Myths of Neural-Symbolic Computation

Authors: Luis C. Lamb

Published in: Dagstuhl Seminar Proceedings, Volume 8041, Recurrent Neural Networks- Models, Capacities, and Applications (2008)


Abstract
The construction of computational cognitive models integrating the connectionist and symbolic paradigms of artificial intelligence is a standing research issue in the field. The combination of logic-based inference and connectionist learning systems may lead to the construction of semantically sound computational cognitive models in artificial intelligence, computer and cognitive sciences. Over the last decades, results regarding the computation and learning of classical reasoning within neural networks have been promising. Nonetheless, there still remains much do be done. Artificial intelligence, cognitive and computer science are strongly based on several non-classical reasoning formalisms, methodologies and logics. In knowledge representation, distributed systems, hardware design, theorem proving, systems specification and verification classical and non-classical logics have had a great impact on theory and real-world applications. Several challenges for neural-symbolic computation are pointed out, in particular for classical and non-classical computation in connectionist systems. We also analyse myths about neural-symbolic computation and shed new light on them considering recent research advances.

Cite as

Luis C. Lamb. The Grand Challenges and Myths of Neural-Symbolic Computation. In Recurrent Neural Networks- Models, Capacities, and Applications. Dagstuhl Seminar Proceedings, Volume 8041, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{lamb:DagSemProc.08041.5,
  author =	{Lamb, Luis C.},
  title =	{{The Grand Challenges  and Myths of Neural-Symbolic Computation}},
  booktitle =	{Recurrent Neural Networks- Models, Capacities, and Applications},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8041},
  editor =	{Luc De Raedt and Barbara Hammer and Pascal Hitzler and Wolfgang Maass},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08041.5},
  URN =		{urn:nbn:de:0030-drops-14233},
  doi =		{10.4230/DagSemProc.08041.5},
  annote =	{Keywords: Connectionist non-classical logics, neural-symbolic computation, non-classical reasoning, computational cognitive models}
}
Document
06431 Working Group Report on Managing and Integrating Data in P2P Databases

Authors: Peter A. Boncz, Angela Bonifati, Arantza Illarramendi, Peter Janacik, Birgitta König-Ries, Wolfgang Lehner, Pedro Jose Marrón, Wolfgang May, Aris Ouksel, Kay Römer, Brahmananda Sapkota, Kai-Uwe Sattler, Heinz Schweppe, Rita Steinmetz, and Can Türker

Published in: Dagstuhl Seminar Proceedings, Volume 6431, Scalable Data Management in Evolving Networks (2007)


Abstract
In this report, to our best recollection, we provide a summary of the working group "Managing and Integrating Data in P2P Databases" of the Dagstuhl Seminar nr. 6431 on "Scalable Data Management in Evolving Neworks", held on October 23-27 in Dagstuhl (Germany).

Cite as

Peter A. Boncz, Angela Bonifati, Arantza Illarramendi, Peter Janacik, Birgitta König-Ries, Wolfgang Lehner, Pedro Jose Marrón, Wolfgang May, Aris Ouksel, Kay Römer, Brahmananda Sapkota, Kai-Uwe Sattler, Heinz Schweppe, Rita Steinmetz, and Can Türker. 06431 Working Group Report on Managing and Integrating Data in P2P Databases. In Scalable Data Management in Evolving Networks. Dagstuhl Seminar Proceedings, Volume 6431, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{boncz_et_al:DagSemProc.06431.3,
  author =	{Boncz, Peter A. and Bonifati, Angela and Illarramendi, Arantza and Janacik, Peter and K\"{o}nig-Ries, Birgitta and Lehner, Wolfgang and Marr\'{o}n, Pedro Jose and May, Wolfgang and Ouksel, Aris and R\"{o}mer, Kay and Sapkota, Brahmananda and Sattler, Kai-Uwe and Schweppe, Heinz and Steinmetz, Rita and T\"{u}rker, Can},
  title =	{{06431 Working Group Report on Managing and Integrating Data in P2P Databases}},
  booktitle =	{Scalable Data Management in Evolving Networks},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6431},
  editor =	{Stefan B\"{o}ttcher and Le Gruenwald and Pedro Jose Marr\'{o}n and Evaggelia Pitoura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06431.3},
  URN =		{urn:nbn:de:0030-drops-9505},
  doi =		{10.4230/DagSemProc.06431.3},
  annote =	{Keywords: P2P database, data integration}
}
Document
06431 Working Group Summary: P2P, Ad Hoc and Sensor Networks – All the Different or All the Same?

Authors: Peter A. Boncz, Angela Bonifati, Joos-Hendrik Böse, Stefan Böttcher, Panos Kypros Chrysanthis, Le Gruenwald, Arantza Illarramendi, Peter Janacik, Birgitta König-Ries, Wolfgang May, Anirban Mondal, Sebastian Obermeier, Aris Ouksel, and George Samaras

Published in: Dagstuhl Seminar Proceedings, Volume 6431, Scalable Data Management in Evolving Networks (2007)


Abstract
Currently, data management technologies are in the process of finding their way into evolving networks, i.e. P2P, ad hoc and wireless sensor networks. We examine the properties, differences and commonalities of the different types of evolving networks, in order to enable the development of adequate technologies suiting their characteristics. We start with presenting definitions for the different network types, before arranging them in a network hierarchy, to gain a clear view of the area. Then, we analyze and compare the example applications for each of the types using different design dimensions. Based on this work, we finally present a comparison of P2P, ad hoc and wireless sensor networks.

Cite as

Peter A. Boncz, Angela Bonifati, Joos-Hendrik Böse, Stefan Böttcher, Panos Kypros Chrysanthis, Le Gruenwald, Arantza Illarramendi, Peter Janacik, Birgitta König-Ries, Wolfgang May, Anirban Mondal, Sebastian Obermeier, Aris Ouksel, and George Samaras. 06431 Working Group Summary: P2P, Ad Hoc and Sensor Networks – All the Different or All the Same?. In Scalable Data Management in Evolving Networks. Dagstuhl Seminar Proceedings, Volume 6431, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{boncz_et_al:DagSemProc.06431.5,
  author =	{Boncz, Peter A. and Bonifati, Angela and B\"{o}se, Joos-Hendrik and B\"{o}ttcher, Stefan and Chrysanthis, Panos Kypros and Gruenwald, Le and Illarramendi, Arantza and Janacik, Peter and K\"{o}nig-Ries, Birgitta and May, Wolfgang and Mondal, Anirban and Obermeier, Sebastian and Ouksel, Aris and Samaras, George},
  title =	{{06431 Working Group Summary: P2P, Ad Hoc and Sensor Networks – All the Different or All the Same?}},
  booktitle =	{Scalable Data Management in Evolving Networks},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6431},
  editor =	{Stefan B\"{o}ttcher and Le Gruenwald and Pedro Jose Marr\'{o}n and Evaggelia Pitoura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06431.5},
  URN =		{urn:nbn:de:0030-drops-9514},
  doi =		{10.4230/DagSemProc.06431.5},
  annote =	{Keywords: P2P, ad hoc, wireless sensor networks, database systems}
}
Document
Automatic Meaning Discovery Using Google

Authors: Rudi Cilibrasi and Paul M.B. Vitanyi

Published in: Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)


Abstract
We survey a new area of parameter-free similarity distance measures useful in data-mining, pattern recognition, learning and automatic semantics extraction. Given a family of distances on a set of objects, a distance is universal up to a certain precision for that family if it minorizes every distance in the family between every two objects in the set, up to the stated precision (we do not require the universal distance to be an element of the family). We consider similarity distances for two types of objects: literal objects that as such contain all of their meaning, like genomes or books, and names for objects. The latter may have literal embodyments like the first type, but may also be abstract like ``red'' or ``christianity.'' For the first type we consider a family of computable distance measures corresponding to parameters expressing similarity according to particular features between pairs of literal objects. For the second type we consider similarity distances generated by web users corresponding to particular semantic relations between the (names for) the designated objects. For both families we give universal similarity distance measures, incorporating all particular distance measures in the family. In the first case the universal distance is based on compression and in the second case it is based on Google page counts related to search terms. In both cases experiments on a massive scale give evidence of the viability of the approaches.

Cite as

Rudi Cilibrasi and Paul M.B. Vitanyi. Automatic Meaning Discovery Using Google. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{cilibrasi_et_al:DagSemProc.06051.3,
  author =	{Cilibrasi, Rudi and Vitanyi, Paul M.B.},
  title =	{{Automatic Meaning Discovery Using Google}},
  booktitle =	{Kolmogorov Complexity and Applications},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6051},
  editor =	{Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.3},
  URN =		{urn:nbn:de:0030-drops-6296},
  doi =		{10.4230/DagSemProc.06051.3},
  annote =	{Keywords: Normalized Compression Distance, Clustering, Clasification, Relative Semantics of Terms, Google, World-Wide-Web, Kolmogorov complexity}
}
Document
Systematic Testing of Embedded Automotive Software - The Classification-Tree Method for Embedded Systems (CTM/ES)

Authors: Mirko Conrad

Published in: Dagstuhl Seminar Proceedings, Volume 4371, Perspectives of Model-Based Testing (2005)


Abstract
The software embedded in automotive control systems increasingly determines the functionality and properties of present-day motor vehicles. The development and test process of the systems and the software embedded becomes the limiting factor. While these challenges, on the development side, are met by employing model-based specification, design, and implementation techniques [KCF+04], satisfactory solutions on the testing side are slow in arriving. With regard to the systematic selection (test design) and the description of test scenarios especially, there is a lot of room for improvement. Thus, a main goal is to effectively minimize these deficits by creating an efficient procedure for the selection and description of test scenarios for embedded automotive software and its integration in the model-based development process. The realization of this idea involves the combination of a classical software testing procedure with a technology, prevalent in the automotive industry, which is used for the description of time-dependent stimuli signals. The result of this combination is the classification-tree method for embedded systems, CTM/ES [Con04]. The classification-tree method for embedded systems complements model-based development by employing a novel approach to the systematic selection and description of the test scenarios for the software embedded in the control systems. CTM/ES allows for the graphic representation of time-variable test scenarios on different levels of abstraction: A problem-oriented, compact representation, adequate for a human tester and containing a high potential for reusability, is gradually being transformed into a solution-oriented technical representation which is suited for the test objects' stimulation. The CTM/ES notation facilitates a consistent representation of test scenarios which may result from different test design techniques. The test design technique which this method is primarily based on, is a data-oriented partitioning of the input domain in equivalence classes. Secondary test design techniques are, for instance, the testing of specific values (or value courses) or requirement-based testing. A domain-specific application pragmatics in the form of agendas supports the methodical execution of individual test activities and the interaction of different test design techniques. The methodology description leads up to an effective test strategy for model-based testing, combining the classification-tree method for embedded systems with structural testing on the model level, and accommodating the different forms of representation of the test object during model-based development. Systems which have been developed in a model-based way can be tested systematically and efficiently by means of the CTM/ES and the tools based thereon, such as the classification-tree editor for embedded systems CTE/ES [CTE/ES], as well as the model-based test environment MTest [LBE+04, MTest].

Cite as

Mirko Conrad. Systematic Testing of Embedded Automotive Software - The Classification-Tree Method for Embedded Systems (CTM/ES). In Perspectives of Model-Based Testing. Dagstuhl Seminar Proceedings, Volume 4371, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{conrad:DagSemProc.04371.4,
  author =	{Conrad, Mirko},
  title =	{{Systematic Testing of Embedded Automotive Software - The Classification-Tree Method for Embedded Systems (CTM/ES)}},
  booktitle =	{Perspectives of Model-Based Testing},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4371},
  editor =	{Ed Brinksma and Wolfgang Grieskamp and Jan Tretmans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04371.4},
  URN =		{urn:nbn:de:0030-drops-3257},
  doi =		{10.4230/DagSemProc.04371.4},
  annote =	{Keywords: Model-based Testing, Classification-tree Method for Embedded Systems (CTM/ES), test design technique, test notation}
}
  • Refine by Author
  • 5 Mulzer, Wolfgang
  • 3 Seiferth, Paul
  • 2 Banyassady, Bahareh
  • 2 Boncz, Peter A.
  • 2 Bonifati, Angela
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Software and its engineering → Data types and structures
  • 1 Software and its engineering → Object oriented languages
  • 1 Theory of computation → Type theory

  • Refine by Keyword
  • 2 Kolmogorov complexity
  • 2 dependency logic
  • 2 interfaces
  • 1 AAL
  • 1 Ambient Assisted Living
  • Show More...

  • Refine by Type
  • 15 document

  • Refine by Publication Year
  • 3 2008
  • 2 2007
  • 2 2017
  • 2 2018
  • 1 2005
  • Show More...

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