Causality in Bounded Petri Nets is MSO Definable

0465187 - MÚ 2017 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
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]
GRANT EU: European Commission(XE) 339691 - FEALORA
Institucionální podpora: RVO:67985840
Klíčová slova: partial order behaviour of Petri nets * monadic second order logic * recognizability
Kód oboru RIV: BA - Obecná matematika
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.
Trvalý link: http://hdl.handle.net/11104/0263851