DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2018.117

Bisimulation Invariant Monadic-Second Order Logic in the Finite

Authors: Achim Blumensath and Felix Wolf

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

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.

Cite as

Achim Blumensath and Felix Wolf. Bisimulation Invariant Monadic-Second Order Logic in the Finite. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 117:1-117:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{blumensath_et_al:LIPIcs.ICALP.2018.117,
  author =	{Blumensath, Achim and Wolf, Felix},
  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 =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.117},
  URN =		{urn:nbn:de:0030-drops-91215},
  doi =		{10.4230/LIPIcs.ICALP.2018.117},
  annote =	{Keywords: bisimulation, monadic second-order logic, composition method}
}

Document

DOI: 10.4230/DagSemProc.05501.4

Holistic Hardware Counter Performance Analysis of Parallel Programs

Authors: Brian J. N. Wylie, Bernd Mohr, and Felix Wolf

Published in: Dagstuhl Seminar Proceedings, Volume 5501, Automatic Performance Analysis (2006)

Abstract

The KOJAK toolkit has been augmented with refined hardware performance counter support, including more convenient measurement specification, additional metric derivations and hierarchical structuring, and an extended algebra for integrating multiple experiments. Comprehensive automated analysis of a hybrid OpenMP/MPI parallel program, the ASC Purple sPPM benchmark, is demonstrated with performance experiments on equisized POWER4-II-based IBM Regatta p690+ cluster, Opteron-based Cray XD1 cluster and UltraSPARC-IV-based Sun Fire E25000 systems. Automatically assessed communication and synchronisation performance properties, combined with a rich set of measured and derived counter metrics, provide a holistic analysis context and facilitate multi-platform comparison.

Cite as

Brian J. N. Wylie, Bernd Mohr, and Felix Wolf. Holistic Hardware Counter Performance Analysis of Parallel Programs. In Automatic Performance Analysis. Dagstuhl Seminar Proceedings, Volume 5501, pp. 1-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{wylie_et_al:DagSemProc.05501.4,
  author =	{Wylie, Brian J. N. and Mohr, Bernd and Wolf, Felix},
  title =	{{Holistic Hardware Counter Performance Analysis of Parallel Programs}},
  booktitle =	{Automatic Performance Analysis},
  pages =	{1--30},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5501},
  editor =	{Hans Michael Gerndt and Allen Malony and Barton P. Miller and Wolfgang Nagel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05501.4},
  URN =		{urn:nbn:de:0030-drops-5071},
  doi =		{10.4230/DagSemProc.05501.4},
  annote =	{Keywords: Parallel program execution tracing, hardware performance counters, automated structured analysis, performance comparison}
}

Search Results

Documents authored by Wolf, Felix

Bisimulation Invariant Monadic-Second Order Logic in the Finite

Abstract

Cite as

Holistic Hardware Counter Performance Analysis of Parallel Programs

Abstract

Cite as

Thanks for your feedback!

Could not send message