Počet záznamů: 1
Causality in Bounded Petri Nets is MSO Definable
- 1.
SYSNO ASEP 0465187 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Causality in Bounded Petri Nets is MSO Definable Tvůrce(i) de Oliveira Oliveira, Mateus (MU-W) RID, SAI, ORCID Zdroj.dok. Logic, Language, Information, and Computation. - Berlin : Springer, 2016 / Väänänen J. ; Hirvonen A. ; de Queiroz R. - ISSN 0302-9743 - ISBN 978-3-662-52920-1 Rozsah stran s. 200-214 Poč.str. 15 s. Forma vydání Tištěná - P Akce 23rd International Workshop on Logic, Information and Computation (WoLLIC 2016) Datum konání 16.08.2016 - 19.08.2016 Místo konání Puebla Země MX - Mexiko Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova partial order behaviour of Petri nets ; monadic second order logic ; recognizability Vědní obor RIV BA - Obecná matematika Institucionální podpora MU-W - RVO:67985840 UT WOS 000389705800013 EID SCOPUS 84981484644 DOI 10.1007/978-3-662-52921-8_13 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2017
Počet záznamů: 1