License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.117
URN: urn:nbn:de:0030-drops-91215
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9121/
Go to the corresponding LIPIcs Volume Portal

Blumensath, Achim ; Wolf, Felix

Bisimulation Invariant Monadic-Second Order Logic in the Finite

pdf-format:
LIPIcs-ICALP-2018-117.pdf (0.4 MB)

Abstract

We consider bisimulation-invariant monadic second-order logic over various classes of finite transition systems. We present several combinatorial characterisations of when the expressive power of this fragment coincides with that of the modal mu-calculus. Using these characterisations we prove for some simple classes of transition systems that this is indeed the case. In particular, we show that, over the class of all finite transition systems with Cantor-Bendixson rank at most k, bisimulation-invariant MSO coincides with L_mu.

BibTeX - Entry

@InProceedings{blumensath_et_al:LIPIcs:2018:9121,
  author =	{Achim Blumensath and Felix Wolf},
  title =	{{Bisimulation Invariant Monadic-Second Order Logic in the Finite}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{117:1--117:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9121},
  URN =		{urn:nbn:de:0030-drops-91215},
  doi =		{10.4230/LIPIcs.ICALP.2018.117},
  annote =	{Keywords: bisimulation, monadic second-order logic, composition method}
}

Keywords: bisimulation, monadic second-order logic, composition method
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI