Fundamenta Informaticae - Volume 44, issue 3

Authors: Busi, Nadia | Pinna, G. Michele

Article Type: Research Article

Abstract: The paper is centered around the study and comparison of truly concurrent semantics for P/T nets with inhibitor and read arcs (called henceforth contextual P/T nets). We start proposing a causal semantics for P/T nets, that we prove to be equivalent to history preserving bisimulation defined on nonsequential processes. Then we develop a conservative extension of the causal semantics to contextual P/T nets and we prove this one to be finer than step semantics. Finally, a …comparison of causal semantics with the process based semantics for contextual P/T systems proposed in \cite{buspin99} is carried out. Show more

Keywords: Contextual Nets, Causal Semantics, Step Semantics, Process Semantics

Citation: Fundamenta Informaticae, vol. 44, no. 3, pp. 209-244, 2000

Authors: Martinek, Pavel

Article Type: Research Article

Abstract: The grammatical inference problem is solved for the class of context-free languages. A context-free language is supposed to be given by means of all its strings. Considering all strings of length bounded by k, context-free grammars G_{j,k} with 1≤j<k are constructed. A~continual increasing of the index~$k$ leads to an~infinite sequence (G_{j,k})_{j<k}. It is proved that G_{j,k} are equivalent for all j≥j_0, k≥k_0 with some positive integers j_0, k_0. Moreover, the equivalences among these grammars can be …recognized on the basis of involved nonterminals and productions only. Show more

Keywords: grammatical inference, context-free grammar, context-free language, identification in the limit

Citation: Fundamenta Informaticae, vol. 44, no. 3, pp. 245-264, 2000

Authors: Payet, Étienne

Article Type: Research Article

Abstract: This paper presents some formal verification-oriented results about the class of graphs associated with Thue specifications. It is shown that this class is closed, up to isomorphism, under synchronized product. It is also established that every rational graph with no edge labeled by the empty word is isomorphic to the graph of a Thue specification. A consequence of this result is that the first-order theory of the graphs of Thue specifications is undecidable. Connections between graphs …of Thue specifications and those of Turing machines are finally investigated. The main result is that the graph of each Thue specification is observationally equivalent to that of a Turing machine but the reverse does not hold. Show more

Keywords: string-rewriting, infinite graphs, synchronized product, Turing machines

Citation: Fundamenta Informaticae, vol. 44, no. 3, pp. 265-290, 2000

Authors: Ślezak, Dominik

Article Type: Research Article

Abstract: We consider the family of normalized decision functions acting over conditional frequency distributions computed from data tables. We draw the connection between such functions and approaches to generating inexact decision rules for the new case classification. We also introduce the family of normalized decision measures corresponding to particular decision functions. They enable us to express efficiency of particular strategies of reasoning with respect to a given data. We show the properties of approximate decision rules …and decision reducts based on normalized decision functions and measures. As a result, we obtain an intuitive and flexible tool for extracting approximate classification models from data. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 44, no. 3, pp. 291-319, 2000