DROPS

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.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}
}

Search Results

Documents authored by Weidner, Thomas

Probabilistic Regular Expressions and MSO Logic on Finite Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message