| BLUMENSATH, Achim and Felix WOLF. Bisimulation Invariant Monadic-Second Order Logic in the Finite. Online. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic. Dagstuhl: Schloss Dagstuhl, 2018, p. 1-13. ISBN 978-3-95977-076-7. Available from: https://dx.doi.org/10.4230/LIPIcs.ICALP.2018.117. |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1423341,
author = {Blumensath, Achim and Wolf, Felix},
address = {Dagstuhl},
booktitle = {45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic},
doi = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.117},
keywords = {bisimulation; monadic second-order logic; composition method},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Dagstuhl},
isbn = {978-3-95977-076-7},
pages = {1-13},
publisher = {Schloss Dagstuhl},
title = {Bisimulation Invariant Monadic-Second Order Logic in the Finite},
year = {2018}
}
TY - JOUR
ID - 1423341
AU - Blumensath, Achim - Wolf, Felix
PY - 2018
TI - Bisimulation Invariant Monadic-Second Order Logic in the Finite
PB - Schloss Dagstuhl
CY - Dagstuhl
SN - 9783959770767
KW - bisimulation
KW - monadic second-order logic
KW - composition method
N2 - 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.
ER -
BLUMENSATH, Achim and Felix WOLF. Bisimulation Invariant Monadic-Second Order Logic in the Finite. Online. In \textit{45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic}. Dagstuhl: Schloss Dagstuhl, 2018, p.~1-13. ISBN~978-3-95977-076-7. Available from: https://dx.doi.org/10.4230/LIPIcs.ICALP.2018.117.
|
