D 2018

Bisimulation Invariant Monadic-Second Order Logic in the Finite

BLUMENSATH, Achim and Felix WOLF

Basic information

Original name

Bisimulation Invariant Monadic-Second Order Logic in the Finite

Authors

BLUMENSATH, Achim (276 Germany, guarantor, belonging to the institution) and Felix WOLF (276 Germany)

Edition

Dagstuhl, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, p. 1-13, 13 pp. 2018

Publisher

Schloss Dagstuhl

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Czech Republic

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/18:00101061

Organization unit

Faculty of Informatics

ISBN

978-3-95977-076-7

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.117

Keywords in English

bisimulation; monadic second-order logic; composition method

Tags

core_A, firank_A, formela-aut
Změněno: 30/4/2019 09:59, RNDr. Pavel Šmerk, Ph.D.

Abstract

V originále

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.

Links

GA17-01035S, research and development project
Name: Algebraická teorie jazyků pro nekonečné stromy
Investor: Czech Science Foundation
Displayed: 4/11/2024 21:39