No label defined (Q3766864)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4024803
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4024803 |
Statements
1987
0 references
formal language
0 references
languages of Petri nets
0 references
monadic second order logic
0 references
0.8351523876190186
0 references
0.824744701385498
0 references
0.7979323267936707
0 references
0.797931969165802
0 references
[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.
0 references