Fundamenta Informaticae - Volume 7, issue 2

Article Type: Other

DOI: 10.3233/FI-1984-7201

Citation: Fundamenta Informaticae, vol. 7, no. 2, pp. i-vi, 1984

Authors: Rozenberg, Grzegorz | Verraedt, Raymond

Article Type: Research Article

Abstract: Petri nets are classified according to the restrictions on the possible in-out structure of nodes of the underlying graphs. Such a classification is investigated separately for the structure of transitions and the structure of places. The classification is done from the language theoretical point of view, i.e. behaviour of a net is expressed by the language it generates. Two approaches are used. Firstly, various classes of nets are compared with respect to the languages of firing sequences they generate. Secondly, the comparison results so obtained are sharpened (often quite drastically) by looking at nets as generators of the so-called subset …languages. Show more

Keywords: Petri nets, graphs, transition and place restrictions, string language, subset language

DOI: 10.3233/FI-1984-7202

Citation: Fundamenta Informaticae, vol. 7, no. 2, pp. 151-190, 1984

Authors: Wojciechowski, Jerzy

Article Type: Research Article

Abstract: In this paper the notion of a nondeterministic finite automaton acting on arbitrary transfinite sequences is introduced. It is a generalization of the finite automaton on finite sequences and the finite automaton on ω -sequences. The basic properties of the behaviour of such automata are proved. The methods are shown how to construct automata accepting classes A ⋃ B, A ⋂ B, A ∘ B, A* , Aω , A# if we have automata accepting classes A and B. We prove that if a TF-automaton having k states accepts anything then it accepts an α -sequence for a …certain, α ∈ { ∑ i = 0 m ω i · a i : ∑ i = 1 m i · a i + a 0 ⩽ k } . Using the foregoing fact, we show that the family of classes definable by TF-automata is not closed with respect to the complement operation, that nondeterministic automata are not equivalent to the deterministic ones and that the emptiness problem for TP-automata is decidable. In the last section we show the construction of TP-automata defining sets {∗α } for α < ω ω and having as few states as possible. Show more

Keywords: finite automata, transfinite sequences, closure properties, emptiness problem, decidability

DOI: 10.3233/FI-1984-7203

Citation: Fundamenta Informaticae, vol. 7, no. 2, pp. 191-223, 1984

Authors: Bavel, Zamir | Grzymała-Busse, Jerzy | Soo Hong, Kwang

Article Type: Research Article

Abstract: Our main results include: Sufficient conditions for two strongly connected automata to have a strongly connected product. Sufficient conditions for the product of two connected automata to be connected and sufficient conditions for it to be not connected. Necessary and sufficient conditions for the product of two strongly connected automata, one of which is total, to be strongly connected. Necessary and sufficient conditions that a singly-generated subautomaton of the product be strongly connected. Necessary and sufficient conditions for the existence of an isomorphic copy of an automaton in its product with another.

Keywords: connected and strongly connected automata, directed product of automata, homomorphisms of automata

DOI: 10.3233/FI-1984-7204

Citation: Fundamenta Informaticae, vol. 7, no. 2, pp. 225-266, 1984