PDL is the bisimulation-invariant fragment of Weak Chain Logic

Authors
  • F. Carreiro
Publication date 2015
Book title Proceedings, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science
Book subtitle LICS 2015: 6-10 July 2015, Kyoto, Japan
ISBN (electronic)
  • 9781479988754
  • 9781479988471
Event 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Pages (from-to) 341-352
Publisher Los Alamitos, California: IEEE Computer Society
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
  • Faculty of Science (FNWI)
Abstract We introduce a new class of parity automata which, on trees, captures the expressive power of weak chain logic. This logic is a variant of monadic second-order logic which quantifies over finite chains. Using this new tool, we show that the bisimulation-invariant fragment of weak chain logic is equivalent to propositional dynamic logic.
Document type Conference contribution
Language English
Published at
https://doi.org/10.1109/LICS.2015.40 (Final published version)
Permalink to this page
Back