10 Search Results for "M�ller, Samuel"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.28
A Sublinear Local Access Implementation for the Chinese Restaurant Process

Authors: Peter Mörters, Christian Sohler, and Stefan Walzer

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
The Chinese restaurant process is a stochastic process closely related to the Dirichlet process that groups sequentially arriving objects into a variable number of classes, such that within each class objects are cyclically ordered. A popular description involves a restaurant, where customers arrive one by one and either sit down next to a randomly chosen customer at one of the existing tables or open a new table. The full state of the process after n steps is given by a permutation of the n objects and cannot be represented in sublinear space. In particular, if we only need specific information about a few objects or classes it would be preferable to obtain the answers without simulating the process completely. A recent line of research [Oded Goldreich et al., 2010; Moni Naor and Asaf Nussboim, 2007; Amartya Shankha Biswas et al., 2020; Guy Even et al., 2021] attempts to provide access to huge random objects without fully instantiating them. Such local access implementations provide answers to a sequence of queries about the random object, following the same distribution as if the object was fully generated. In this paper, we provide a local access implementation for a generalization of the Chinese restaurant process described above. Our implementation can be used to answer any sequence of adaptive queries about class affiliation of objects, number and sizes of classes at any time, position of elements within a class, or founding time of a class. The running time per query is polylogarithmic in the total size of the object, with high probability. Our approach relies on some ideas from the recent local access implementation for preferential attachment trees by Even et al. [Guy Even et al., 2021]. Such trees are related to the Chinese restaurant process in the sense that both involve a "rich-get-richer" phenomenon. A novel ingredient in our implementation is to embed the process in continuous time, in which the evolution of the different classes becomes stochastically independent [Joyce and Tavaré, 1987]. This independence is used to keep the probabilistic structure manageable even if many queries have already been answered. As similar embeddings are available for a wide range of urn processes [Krishna B. Athreya and Samuel Karlin, 1968], we believe that our approach may be applicable more generally. Moreover, local access implementations for birth and death processes that we encounter along the way may be of independent interest.
Cite as

Peter Mörters, Christian Sohler, and Stefan Walzer. A Sublinear Local Access Implementation for the Chinese Restaurant Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{morters_et_al:LIPIcs.APPROX/RANDOM.2022.28,
  author =	{M\"{o}rters, Peter and Sohler, Christian and Walzer, Stefan},
  title =	{{A Sublinear Local Access Implementation for the Chinese Restaurant Process}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.28},
  URN =		{urn:nbn:de:0030-drops-171500},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.28},
  annote =	{Keywords: Chinese restaurant process, Dirichlet process, sublinear time algorithm, random recursive tree, random permutation, random partition, Ewens distribution, simulation, local access implementation, continuous time embedding}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.107
Keep That Card in Mind: Card Guessing with Limited Memory

Authors: Boaz Menuhin and Moni Naor

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
A card guessing game is played between two players, Guesser and Dealer. At the beginning of the game, the Dealer holds a deck of n cards (labeled 1, ..., n). For n turns, the Dealer draws a card from the deck, the Guesser guesses which card was drawn, and then the card is discarded from the deck. The Guesser receives a point for each correctly guessed card. With perfect memory, a Guesser can keep track of all cards that were played so far and pick at random a card that has not appeared so far, yielding in expectation ln n correct guesses, regardless of how the Dealer arranges the deck. With no memory, the best a Guesser can do will result in a single guess in expectation. We consider the case of a memory bounded Guesser that has m < n memory bits. We show that the performance of such a memory bounded Guesser depends much on the behavior of the Dealer. In more detail, we show that there is a gap between the static case, where the Dealer draws cards from a properly shuffled deck or a prearranged one, and the adaptive case, where the Dealer draws cards thoughtfully, in an adversarial manner. Specifically: 1) We show a Guesser with O(log² n) memory bits that scores a near optimal result against any static Dealer. 2) We show that no Guesser with m bits of memory can score better than O(√m) correct guesses against a random Dealer, thus, no Guesser can score better than min {√m, ln n}, i.e., the above Guesser is optimal. 3) We show an efficient adaptive Dealer against which no Guesser with m memory bits can make more than ln m + 2 ln log n + O(1) correct guesses in expectation. These results are (almost) tight, and we prove them using compression arguments that harness the guessing strategy for encoding.
Cite as

Boaz Menuhin and Moni Naor. Keep That Card in Mind: Card Guessing with Limited Memory. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 107:1-107:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{menuhin_et_al:LIPIcs.ITCS.2022.107,
  author =	{Menuhin, Boaz and Naor, Moni},
  title =	{{Keep That Card in Mind: Card Guessing with Limited Memory}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{107:1--107:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.107},
  URN =		{urn:nbn:de:0030-drops-157039},
  doi =		{10.4230/LIPIcs.ITCS.2022.107},
  annote =	{Keywords: Adaptivity vs Non-adaptivity, Adversarial Robustness, Card Guessing, Compression Argument, Information Theory, Streaming Algorithms, Two Player Game}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.50
Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach

Authors: Lars Jaffke, Mateus de Oliveira Oliveira, and Hans Raj Tiwary

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+|G|) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can be embedded in the n-clique K_n, a connected graph with n vertices. In this work, we show that the minimum size of a context-free grammar generating a finite permutation group G⊑ 𝕊_n can be upper bounded by three structural parameters of connected graphs embedding G: the number of vertices, the treewidth, and the maximum degree. More precisely, we show that any permutation group G ⊑ 𝕊_n that can be embedded into a connected graph with m vertices, treewidth k, and maximum degree Δ, can also be generated by a context-free grammar of size 2^{O(kΔlogΔ)}⋅ m^{O(k)}. By combining our upper bound with a connection established by Pesant, Quimper, Rousseau and Sellmann [Gilles Pesant et al., 2009] between the extension complexity of a permutation group and the grammar complexity of a formal language, we also get that these permutation groups can be represented by polytopes of extension complexity 2^{O(kΔlogΔ)}⋅ m^{O(k)}. The above upper bounds can be used to provide trade-offs between the index of permutation groups, and the number of vertices, treewidth and maximum degree of connected graphs embedding these groups. In particular, by combining our main result with a celebrated 2^{Ω(n)} lower bound on the grammar complexity of the symmetric group 𝕊_n due to Glaister and Shallit [Glaister and Shallit, 1996] we have that connected graphs of treewidth o(n/log n) and maximum degree o(n/log n) embedding subgroups of 𝕊_n of index 2^{cn} for some small constant c must have n^{ω(1)} vertices. This lower bound can be improved to exponential on graphs of treewidth n^{ε} for ε < 1 and maximum degree o(n/log n).
Cite as

Lars Jaffke, Mateus de Oliveira Oliveira, and Hans Raj Tiwary. Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.MFCS.2020.50,
  author =	{Jaffke, Lars and de Oliveira Oliveira, Mateus and Tiwary, Hans Raj},
  title =	{{Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{50:1--50:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.50},
  URN =		{urn:nbn:de:0030-drops-127161},
  doi =		{10.4230/LIPIcs.MFCS.2020.50},
  annote =	{Keywords: Permutation Groups, Context Free Grammars, Extension Complexity, Graph Embedding Complexity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSCD.2020.2
A Modal Analysis of Metaprogramming, Revisited (Invited Talk)

Authors: Brigitte Pientka

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

Abstract
Metaprogramming is the art of writing programs that produce or manipulate other programs. This opens the possibility to eliminate boilerplate code and exploit domain-specific knowledge to build high-performance programs. Unfortunately, designing language extensions to support type-safe multi-staged metaprogramming remains very challenging. In this talk, we outline a modal type-theoretic foundation for multi-staged metaprogramming which supports the generation and the analysis of polymorphic code. It has two main ingredients: first, we exploit contextual modal types to describe open code together with the context in which it is meaningful; second, we model code as a higher-order abstract syntax (HOAS) tree within a context. These two ideas provide the appropriate abstractions for both generating and pattern matching on open code without committing to a concrete representation of variable binding and contexts. Our work is a first step towards building a general type-theoretic foundation for multi-staged metaprogramming which on the one hand enforces strong type guarantees and on the other hand makes it easy to generate and manipulate code. This will allow us to exploit the full potential of metaprogramming without sacrificing reliability of and trust in the code we are producing and running.
Cite as

Brigitte Pientka. A Modal Analysis of Metaprogramming, Revisited (Invited Talk). In 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 167, pp. 2:1-2:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{pientka:LIPIcs.FSCD.2020.2,
  author =	{Pientka, Brigitte},
  title =	{{A Modal Analysis of Metaprogramming, Revisited}},
  booktitle =	{5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)},
  pages =	{2:1--2:3},
  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.2},
  URN =		{urn:nbn:de:0030-drops-123242},
  doi =		{10.4230/LIPIcs.FSCD.2020.2},
  annote =	{Keywords: Type systems, Metaprogramming, Modal Type System}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.70
Retracting Graphs to Cycles

Authors: Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the mapping to the cycle is the identity map. This problem has its roots in the rich theory of retraction of topological spaces, and has strong ties to well-studied metric embedding problems such as minimum bandwidth and 0-extension. Our first result is an O(min{k, sqrt{n}})-approximation for retracting any graph on n nodes to a cycle with k nodes. We also show a surprising connection to Sperner’s Lemma that rules out the possibility of improving this result using certain natural convex relaxations of the problem. Nevertheless, if the problem is restricted to planar graphs, we show that we can overcome these integrality gaps by giving an optimal combinatorial algorithm, which is the technical centerpiece of the paper. Building on our planar graph algorithm, we also obtain a constant-factor approximation algorithm for retraction of points in the Euclidean plane to a uniform cycle.
Cite as

Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram. Retracting Graphs to Cycles. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 70:1-70:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{haney_et_al:LIPIcs.ICALP.2019.70,
  author =	{Haney, Samuel and Liaee, Mehraneh and Maggs, Bruce M. and Panigrahi, Debmalya and Rajaraman, Rajmohan and Sundaram, Ravi},
  title =	{{Retracting Graphs to Cycles}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{70:1--70:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.70},
  URN =		{urn:nbn:de:0030-drops-106462},
  doi =		{10.4230/LIPIcs.ICALP.2019.70},
  annote =	{Keywords: Graph algorithms, Graph embedding, Planar graphs, Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.65
Analysing Survey Propagation Guided Decimationon Random Formulas

Authors: Samuel Hetterich

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Let vec(theta) be a uniformly distributed random k-SAT formula with n variables and m clauses. For clauses/variables ratio m/n <= r_{k-SAT} ~ 2^k*ln(2) the formula vec(theta) is satisfiable with high probability. However, no efficient algorithm is known to provably find a satisfying assignment beyond m/n ~ 2k*ln(k)/k with a non-vanishing probability. Non-rigorous statistical mechanics work on k-CNF led to the development of a new efficient "message passing algorithm" called Survey Propagation Guided Decimation [Mézard et al., Science 2002]. Experiments conducted for k=3,4,5 suggest that the algorithm finds satisfying assignments close to r_{k-SAT}. However, in the present paper we prove that the basic version of Survey Propagation Guided Decimation fails to solve random k-SAT formulas efficiently already for m/n = 2^{k}(1 + epsilon_k)*ln(k)/k with lim_{k -> infinity} epsilon_k = 0 almost a factor k below r_{k-SAT}.
Cite as

Samuel Hetterich. Analysing Survey Propagation Guided Decimationon Random Formulas. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 65:1-65:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hetterich:LIPIcs.ICALP.2016.65,
  author =	{Hetterich, Samuel},
  title =	{{Analysing Survey Propagation Guided Decimationon Random Formulas}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{65:1--65:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.65},
  URN =		{urn:nbn:de:0030-drops-62197},
  doi =		{10.4230/LIPIcs.ICALP.2016.65},
  annote =	{Keywords: Survey Propagation Guided Decimation, Message Passing Algorithm, Graph Theory, Random k-SAT}
}
Document
DOI: 10.4230/OASIcs.CMN.2013.36
The Disappearance of Moral Choice in Serially Reproduced Narratives

Authors: Fritz Breithaupt, Kevin M. Gardner, John K. Kruschke, Torrin M. Liddell, and Samuel Zorowitz

Published in: OASIcs, Volume 32, 2013 Workshop on Computational Models of Narrative

Abstract
How do narratives influence moral decision-making? Our ongoing studies use serial reproduction of narratives, that is multiple retellings as in the telephone game, of morally ambiguous situations. In particular, we tested stories that include a minor misdemeanor, but leave open whether the wrongdoer will be punished by a bystander. It turns out that serial reproduction (retelling) of stories tends to eliminate the possibility of intervention by the bystander under certain conditions. We reason that this effect can be explained either by preferences of the readers or by the reader's discomfort to get involved. A second finding is that retellings of third-person narratives of moral situations lead to a higher degree of change and invention of the outcome than first-person narratives.
Cite as

Fritz Breithaupt, Kevin M. Gardner, John K. Kruschke, Torrin M. Liddell, and Samuel Zorowitz. The Disappearance of Moral Choice in Serially Reproduced Narratives. In 2013 Workshop on Computational Models of Narrative. Open Access Series in Informatics (OASIcs), Volume 32, pp. 36-42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{breithaupt_et_al:OASIcs.CMN.2013.36,
  author =	{Breithaupt, Fritz and Gardner, Kevin M. and Kruschke, John K. and Liddell, Torrin M. and Zorowitz, Samuel},
  title =	{{The Disappearance of Moral Choice in Serially Reproduced Narratives}},
  booktitle =	{2013 Workshop on Computational Models of Narrative},
  pages =	{36--42},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-57-6},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{32},
  editor =	{Finlayson, Mark A. and Fisseni, Bernhard and L\"{o}we, Benedikt and Meister, Jan Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2013.36},
  URN =		{urn:nbn:de:0030-drops-41386},
  doi =		{10.4230/OASIcs.CMN.2013.36},
  annote =	{Keywords: Narrative, moral stories, side taking, serial reproduction, first-person versus third person narrative}
}
Document
DOI: 10.4230/DagSemProc.09061.3
A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix

Authors: Samuel I. Daitch and Daniel A. Spielman

Published in: Dagstuhl Seminar Proceedings, Volume 9061, Combinatorial Scientific Computing (2009)

Abstract
We present an algorithm for solving a linear system in a symmetric M-matrix. In particular, for $n times n$ symmetric M-matrix $M$, we show how to find a diagonal matrix $D$ such that $DMD$ is diagonally-dominant. To compute $D$, the algorithm must solve $O{log n}$ linear systems in diagonally-dominant matrices. If we solve these diagonally-dominant systems approximately using the Spielman-Teng nearly-linear time solver, then we obtain an algorithm for approximately solving linear systems in symmetric M-matrices, for which the expected running time is also nearly-linear.
Cite as

Samuel I. Daitch and Daniel A. Spielman. A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix. In Combinatorial Scientific Computing. Dagstuhl Seminar Proceedings, Volume 9061, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{daitch_et_al:DagSemProc.09061.3,
  author =	{Daitch, Samuel I. and Spielman, Daniel A.},
  title =	{{A Nearly-Linear Time Algorithm for Approximately Solving Linear Systems in a Symmetric M-Matrix}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09061.3},
  URN =		{urn:nbn:de:0030-drops-20803},
  doi =		{10.4230/DagSemProc.09061.3},
  annote =	{Keywords: M-matrix, diagonally-dominant matrix, linear system solver, iterative algorithm, randomized algorithm, network flow, gain graph}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1740
Runtime Monitoring of Metric First-order Temporal Properties

Authors: David Basin, Felix Klaedtke, Samuel Müller, and Birgit Pfitzmann

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract
We introduce a novel approach to the runtime monitoring of complex system properties. In particular, we present an online algorithm for a safety fragment of metric first-order temporal logic that is considerably more expressive than the logics supported by prior monitoring methods. Our approach, based on automatic structures, allows the unrestricted use of negation, universal and existential quantification over infinite domains, and the arbitrary nesting of both past and bounded future operators. Moreover, we show how to optimize our approach for the common case where structures consist of only finite relations, over possibly infinite domains. Under an additional restriction, we prove that the space consumed by our monitor is polynomially bounded by the cardinality of the data appearing in the processed prefix of the temporal structure being monitored.
Cite as

David Basin, Felix Klaedtke, Samuel Müller, and Birgit Pfitzmann. Runtime Monitoring of Metric First-order Temporal Properties. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 49-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{basin_et_al:LIPIcs.FSTTCS.2008.1740,
  author =	{Basin, David and Klaedtke, Felix and M\"{u}ller, Samuel and Pfitzmann, Birgit},
  title =	{{Runtime Monitoring of Metric First-order Temporal Properties}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{49--60},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1740},
  URN =		{urn:nbn:de:0030-drops-17404},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1740},
  annote =	{Keywords: Runtime Monitoring, Metric First-order Temporal Logic, Automatic Structures, Temporal Databases}
}
Document
DOI: 10.4230/DagSemProc.07361.3
A Case for Deconstructing Hardware Transactional Memory Systems

Authors: Mark D. Hill, Derek Hower, Kevin E. Moore, Michael M. Swift, Haris Volos, and David A. Wood

Published in: Dagstuhl Seminar Proceedings, Volume 7361, Programming Models for Ubiquitous Parallelism (2008)

Abstract
Major hardware and software vendors are curious about transactional memory (TM), but are understandably cautious about committing to hardware changes. Our thesis is that deconstructing transactional memory into separate, interchangeable components facilitates TM adoption in two ways. First, it aids hardware TM refinement, allowing vendors to adopt TM earlier, knowing that they can more easily refine aspects later. Second, it enables the components to be applied to other uses, including reliability, security, performance, and correctness, providing value even if TM is not widely used. We develop some evidence for our thesis via experience with LogTM variants and preliminary case studies of scalable watchpoints and race recording for deterministic replay.
Cite as

Mark D. Hill, Derek Hower, Kevin E. Moore, Michael M. Swift, Haris Volos, and David A. Wood. A Case for Deconstructing Hardware Transactional Memory Systems. In Programming Models for Ubiquitous Parallelism. Dagstuhl Seminar Proceedings, Volume 7361, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hill_et_al:DagSemProc.07361.3,
  author =	{Hill, Mark D. and Hower, Derek and Moore, Kevin E. and Swift, Michael M. and Volos, Haris and Wood, David A.},
  title =	{{A Case for Deconstructing Hardware Transactional Memory Systems}},
  booktitle =	{Programming Models for Ubiquitous Parallelism},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7361},
  editor =	{Albert Cohen and Mar{\'\i}a J. Garzar\'{a}n and Christian Lengauer and Samuel P. Midkiff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07361.3},
  URN =		{urn:nbn:de:0030-drops-13759},
  doi =		{10.4230/DagSemProc.07361.3},
  annote =	{Keywords: Hardware transactional memory}
}
  • Refine by Author
  • 1 Basin, David
  • 1 Breithaupt, Fritz
  • 1 Daitch, Samuel I.
  • 1 Gardner, Kevin M.
  • 1 Haney, Samuel
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Adversary models
  • 1 Theory of computation → Algebraic language theory
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Generating random combinatorial structures
  • 1 Theory of computation → Lambda calculus
  • Show More...

  • Refine by Keyword
  • 1 Adaptivity vs Non-adaptivity
  • 1 Adversarial Robustness
  • 1 Approximation algorithms
  • 1 Automatic Structures
  • 1 Card Guessing
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 2 2008
  • 2 2020
  • 2 2022
  • 1 2009
  • 1 2013
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact