5 Search Results for "Luttenberger, Michael"


Document
Computing the Longest Common Prefix of a Context-free Language in Polynomial Time

Authors: Michael Luttenberger, Raphaela Palenta, and Helmut Seidl

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)


Abstract
We present two structural results concerning the longest common prefixes of non-empty languages. First, we show that the longest common prefix of the language generated by a context-free grammar of size N equals the longest common prefix of the same grammar where the heights of the derivation trees are bounded by 4N. Second, we show that each non-empty language L has a representative subset of at most three elements which behaves like L w.r.t. the longest common prefix as well as w.r.t. longest common prefixes of L after unions or concatenations with arbitrary other languages. From that, we conclude that the longest common prefix, and thus the longest common suffix, of a context-free language can be computed in polynomial time.

Cite as

Michael Luttenberger, Raphaela Palenta, and Helmut Seidl. Computing the Longest Common Prefix of a Context-free Language in Polynomial Time. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{luttenberger_et_al:LIPIcs.STACS.2018.48,
  author =	{Luttenberger, Michael and Palenta, Raphaela and Seidl, Helmut},
  title =	{{Computing the Longest Common Prefix of a Context-free Language in Polynomial Time}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{48:1--48:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.48},
  URN =		{urn:nbn:de:0030-drops-84828},
  doi =		{10.4230/LIPIcs.STACS.2018.48},
  annote =	{Keywords: longest common prefix, context-free languages, combinatorics on words}
}
Document
An adaptive protocol for distributed beamforming

Authors: Stephan Sigg and Michael Beigl

Published in: OASIcs, Volume 17, 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)


Abstract
We study distributed adaptive beamforming in networks of wireless nodes. In particular, we observe that for the synchronisation of carrier phases, distinct algorithmic configurations are optimal in various environmental settings and propose a protocol that utilises organic computing principles to find optimum parameters. Furthermore, we study the impact of different modulation schemes on the bit error rate of a signal sequence transmitted collaboratively by distributed devices via adaptive beamforming.

Cite as

Stephan Sigg and Michael Beigl. An adaptive protocol for distributed beamforming. In 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011). Open Access Series in Informatics (OASIcs), Volume 17, pp. 38-48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{sigg_et_al:OASIcs.KiVS.2011.38,
  author =	{Sigg, Stephan and Beigl, Michael},
  title =	{{An adaptive protocol for distributed beamforming}},
  booktitle =	{17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)},
  pages =	{38--48},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-27-9},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{17},
  editor =	{Luttenberger, Norbert and Peters, Hagen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.KiVS.2011.38},
  URN =		{urn:nbn:de:0030-drops-29565},
  doi =		{10.4230/OASIcs.KiVS.2011.38},
  annote =	{Keywords: Distributed beamforming, Adaptive synchronisation protocol}
}
Document
A Privacy-Preserving Social P2P Infrastructure for People-Centric Sensing

Authors: Michael Dürr and Kevin Wiesner

Published in: OASIcs, Volume 17, 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)


Abstract
The rapid miniaturization and integration of sensor technologies into mobile Internet devices combined with Online Social Networks allows for enhanced sensor information querying, subscription, and task placement within People-Centric Sensing networks. However, PCS systems which exploit knowledge about OSN user profiles and context information for enhanced service provision might cause an unsolicited application and dissemination of highly personal and sensitive data. In this paper, we propose a protocol extension to our OSN design Vegas which enables secure, privacy-preserving, and trustful P2P communication between PCS participants. By securing knowledge about social links with standard public key cryptography, we achieve a degree of anonymity at a trust level which is almost good as that provided by a centralized trusted third party.

Cite as

Michael Dürr and Kevin Wiesner. A Privacy-Preserving Social P2P Infrastructure for People-Centric Sensing. In 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011). Open Access Series in Informatics (OASIcs), Volume 17, pp. 176-181, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{durr_et_al:OASIcs.KiVS.2011.176,
  author =	{D\"{u}rr, Michael and Wiesner, Kevin},
  title =	{{A Privacy-Preserving Social P2P Infrastructure for People-Centric Sensing}},
  booktitle =	{17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)},
  pages =	{176--181},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-27-9},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{17},
  editor =	{Luttenberger, Norbert and Peters, Hagen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.KiVS.2011.176},
  URN =		{urn:nbn:de:0030-drops-29695},
  doi =		{10.4230/OASIcs.KiVS.2011.176},
  annote =	{Keywords: People-Centric Sensing, Online Social Networks, P2P, Privacy, Trust}
}
Document
Efficient Distributed Intrusion Detection applying Multi Step Signatures

Authors: Michael Vogel and Sebastian Schmerl

Published in: OASIcs, Volume 17, 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)


Abstract
Intrusion Detection Systems (IDS) offer valuable measures to cope with today’s attacks on computers and networks. But the increasing performance of networks and end systems and the growing complexity of IT systems lead to rapidly growing volumes of observation data and large signature bases. Therefore, IDS are forced to drop observations in high load situations offering chances to attackers to act undetectable. We introduce an efficient dynamically adaptable, distributed approach for a multi-step signature based IDS. Finally, we discuss initial performance evaluations of a prototype implementation and motivate future work scopes.

Cite as

Michael Vogel and Sebastian Schmerl. Efficient Distributed Intrusion Detection applying Multi Step Signatures. In 17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011). Open Access Series in Informatics (OASIcs), Volume 17, pp. 188-193, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{vogel_et_al:OASIcs.KiVS.2011.188,
  author =	{Vogel, Michael and Schmerl, Sebastian},
  title =	{{Efficient Distributed Intrusion Detection applying Multi Step Signatures}},
  booktitle =	{17th GI/ITG Conference on Communication in Distributed Systems (KiVS 2011)},
  pages =	{188--193},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-27-9},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{17},
  editor =	{Luttenberger, Norbert and Peters, Hagen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.KiVS.2011.188},
  URN =		{urn:nbn:de:0030-drops-29716},
  doi =		{10.4230/OASIcs.KiVS.2011.188},
  annote =	{Keywords: Computer Security, Distributed Intrusion Detection, Attack Signatures}
}
Document
Convergence Thresholds of Newton's Method for Monotone Polynomial Equations

Authors: Javier Esparza, Stefan Kiefer, and Michael Luttenberger

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)


Abstract
Monotone systems of polynomial equations (MSPEs) are systems of fixed-point equations $X_1 = f_1(X_1, ldots, X_n),$ $ldots, X_n = f_n(X_1, ldots, X_n)$ where each $f_i$ is a polynomial with positive real coefficients. The question of computing the least non-negative solution of a given MSPE $vec X = vec f(vec X)$ arises naturally in the analysis of stochastic models such as stochastic context-free grammars, probabilistic pushdown automata, and back-button processes. Etessami and Yannakakis have recently adapted Newton's iterative method to MSPEs. In a previous paper we have proved the existence of a threshold $k_{vec f}$ for strongly connected MSPEs, such that after $k_{vec f}$ iterations of Newton's method each new iteration computes at least 1 new bit of the solution. However, the proof was purely existential. In this paper we give an upper bound for $k_{vec f}$ as a function of the minimal component of the least fixed-point $muvec f$ of $vec f(vec X)$. Using this result we show that $k_{vec f}$ is at most single exponential resp. linear for strongly connected MSPEs derived from probabilistic pushdown automata resp. from back-button processes. Further, we prove the existence of a threshold for arbitrary MSPEs after which each new iteration computes at least $1/w2^h$ new bits of the solution, where $w$ and $h$ are the width and height of the DAG of strongly connected components.

Cite as

Javier Esparza, Stefan Kiefer, and Michael Luttenberger. Convergence Thresholds of Newton's Method for Monotone Polynomial Equations. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 289-300, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{esparza_et_al:LIPIcs.STACS.2008.1351,
  author =	{Esparza, Javier and Kiefer, Stefan and Luttenberger, Michael},
  title =	{{Convergence Thresholds of Newton's Method for Monotone Polynomial Equations}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{289--300},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1351},
  URN =		{urn:nbn:de:0030-drops-13516},
  doi =		{10.4230/LIPIcs.STACS.2008.1351},
  annote =	{Keywords: Newton's Method, Fixed-Point Equations, Formal Verification of Software, Probabilistic Pushdown Systems}
}
  • Refine by Author
  • 2 Luttenberger, Michael
  • 1 Beigl, Michael
  • 1 Dürr, Michael
  • 1 Esparza, Javier
  • 1 Kiefer, Stefan
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Adaptive synchronisation protocol
  • 1 Attack Signatures
  • 1 Computer Security
  • 1 Distributed Intrusion Detection
  • 1 Distributed beamforming
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 3 2011
  • 1 2008
  • 1 2018

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