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

      0 references
      1987
      0 references
      formal language
      0 references
      languages of Petri nets
      0 references
      monadic second order logic
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references