1 Search Results for "Weidner, Thomas"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.503
Probabilistic Regular Expressions and MSO Logic on Finite Trees

Authors: Thomas Weidner

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
We introduce probabilistic regular tree expressions and give a Kleene-like theorem for probabilistic tree automata (PTA). Furthermore, we define probabilistic MSO logic. This logic is more expressive than PTA. We define bottom-up PTA, which are strictly more expressive than PTA. Using bottom-up PTA, we prove a Büchi-like theorem for probabilistic MSO logic. We obtain a Nivat-style theorem as an additional result.
Cite as

Thomas Weidner. Probabilistic Regular Expressions and MSO Logic on Finite Trees. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 503-516, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{weidner:LIPIcs.FSTTCS.2015.503,
  author =	{Weidner, Thomas},
  title =	{{Probabilistic Regular Expressions and MSO Logic on Finite Trees}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{503--516},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.503},
  URN =		{urn:nbn:de:0030-drops-56303},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.503},
  annote =	{Keywords: Probabilistic Regular Expressions, MSO Logic, Tree Automata}
}
  • Refine by Author
  • 1 Weidner, Thomas

  • Refine by Classification

  • Refine by Keyword
  • 1 MSO Logic
  • 1 Probabilistic Regular Expressions
  • 1 Tree Automata

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

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