Number of the records: 1
Causality in Bounded Petri Nets is MSO Definable
- 1.0465187 - MÚ 2017 RIV DE eng C - Conference Paper (international conference)
de Oliveira Oliveira, Mateus
Causality in Bounded Petri Nets is MSO Definable.
Logic, Language, Information, and Computation. Berlin: Springer, 2016 - (Väänänen, J.; Hirvonen, A.; de Queiroz, R.), s. 200-214. Lecture Notes in Computer Science, 9803. ISBN 978-3-662-52920-1. ISSN 0302-9743.
[23rd International Workshop on Logic, Information and Computation (WoLLIC 2016). Puebla (MX), 16.08.2016-19.08.2016]
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : partial order behaviour of Petri nets * monadic second order logic * recognizability
Subject RIV: BA - General Mathematics
http://link.springer.com/chapter/10.1007/978-3-662-52921-8_13
In this work we show that the causal behaviour of any bounded Petri net is definable in monadic second order (MSO) logic. Our proof relies in a definability vs recognizability result for DAGs whose edges and vertices can be covered by a constant number of paths. Our notion of recognizability is defined in terms of saturated slice automata, a formalism for the specification of infinite families of graphs. We show that a family G of k-coverable DAGs is recognizable by a saturated slice automaton if and only if G is definable in monadic second order logic. This result generalizes Büchi’s theorem from the context of strings, to the context of k-coverable DAGs.
Permanent Link: http://hdl.handle.net/11104/0263851
File Download Size Commentary Version Access deOliveiraOliveira4.pdf 2 334.2 KB Publisher’s postprint require
Number of the records: 1