scientific article; zbMATH DE number 4024803
[For the entire collection see Zbl 0621.00028.] The study of the relations between formal language theory and symbolic logic, started by Büchi in 1960, has had in the last few years a revival, for example with the work of \textit{W. Thomas} [Inf. Control 48, 261-283 (1981; Zbl 0478.03020)]. These studies dealt mainly with languages accepted by finite automata, describing their finite or infinite behaviour. In a paper of \textit{M. Parigot} and the author [Theor. Comput. Sci. 39, 155-169 (1985; Zbl 0605.68049)], the languages of Petri nets - as a description of their finite (sequential) behaviour - were considered for the first time from a logical point of view. Now, our work deals with the infinite (sequential) behaviour of Petri nets. In this article we will show that a certain class of sentences of the monadic second order logic \({\mathcal L}=\{\leq\), \((P_{\alpha})_{\alpha \in \Sigma}\), \(\leq_ g\), \(=_ g\}\) (introduced by \textit{M. Parigot} and the author [loc. cit. and Lect. Notes Comput. Sci. 222, 346-361 (1986; Zbl 0613.68028)]) exactly characterize the infinitary or \(\omega\)-languages of Petri nets over an alphabet \(\Sigma\), defined by their 3-behaviour (according to Valk and Carstensen's definition [\textit{R. Valk}, Theor. Comput. Sci. 25, 311-341 (1983; Zbl 0559.68057); \textit{H. Carstensen} and \textit{R. Valk}, Lect. Notes Comput. Sci. 188, 83-100 (1985; Zbl 0571.68045)]). As an application, we will give some examples of non trivial Petri net \(\omega\)-languages, whose complements are not Petri net \(\omega\)- languages. They are found by a logical consideration, which grew out from our characterization theorem. Finally, the \(\omega\)-languages defined by the other behaviours of Petri nets, defined by R. Valk and H. Carstensen [loc. cit.], will be considered and results of their definability in \({\mathcal L}\) can be given. But for these classes of \(\omega\)-languages the reciprocal, i.e. that each \({\mathcal L}\)-sentence of the corresponding type defines a language of the class, is not true. We justify this with several counterexamples.
- A logical approach of Petri net languages
- Time-based expressivity of time Petri nets for system specification
- Closure properties of locally finite \(\omega\)-languages
- Infinite behaviour of Petri nets
- Causality in bounded Petri nets is MSO definable
- Synthesis of Petri Nets from Term Based Representations of Infinite Partial Languages
- scientific article; zbMATH DE number 3982543 (Why is no real title available?)
- scientific article; zbMATH DE number 3992937 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3766864)