Fundamenta Informaticae - Volume 123, issue 3

Authors: Balaguer, Sandie | Chatain, Thomas | Haar, Stefan

Article Type: Research Article

Abstract: Occurrence nets are a well known partial order model for the concurrent behavior of Petri nets. The causality and conflict relations between events, which are explicitly represented in occurrence nets, induce logical dependencies between event occurrences: the occurrence of an event e in a run implies that all its causal predecessors also occur, and that no event in conflict with e occurs. But these structural relations do not express all the logical dependencies between event occurrences in maximal runs: in particular, the occurrence of e in any maximal run may imply the occurrence of another event that is not a …causal predecessor of e, in that run. The reveals relation has been introduced to express this dependency between two events. Here we generalize the reveals relation to express more general dependencies, involving more than two events, and we introduce ERL logic to express them as boolean formulas. Finally we answer the synthesis problem that arises: given an ERL formula �, is there an occurrence net 𝒩 such that � describes exactly the dependencies between the events of 𝒩? Show more

Keywords: synthesis of concurrent systems, occurrence nets, event logics, Petri nets, maximal runs

DOI: 10.3233/FI-2013-809

Citation: Fundamenta Informaticae, vol. 123, no. 3, pp. 245-272, 2013

Authors: Cichoń, Jacek | Klonowski, Marek

Article Type: Research Article

Abstract: In this paper we study the efficiency of information flooding protocols in various communication networks, and in the presence of random faults. We show big differences between the flooding performance of networks with a seemingly similar structure. Since real-life systems usually consist of a moderate number of devices, the analysis presented in this paper is not limited to the asymptotic behavior of the flooding protocol. Instead, exact formulas are provided whenever possible. The presented results can be useful building blocks for the analysis of other, more sophisticated protocols. In particular, they may be used for planning and analyzing sensors network …deployed in an environment subject to communication failures. Show more

Keywords: flooding protocol, communication networks with failures, geometric distribution, Markov chain

DOI: 10.3233/FI-2013-810

Citation: Fundamenta Informaticae, vol. 123, no. 3, pp. 273-287, 2013

Authors: Meduna, Alexander | Zemek, Petr

Article Type: Research Article

Abstract: Consider ET0L grammars. Modify them such that a set of permitting symbols and a set of forbidding symbols are attached to each of their rules, just like in random context grammars. A rule like this can rewrite a symbol if each of its permitting symbols occurs to the left of the symbol to be rewritten in the current sentential form while each of its forbidding symbols does not occur there. ET0L grammars modified in this way are referred to as left random context ET0L grammars, and they represent the principal subject of the investigation in this paper. We prove that …these grammars characterize the family of recursively enumerable languages, and without erasing rules, they characterize the family of context-sensitive languages. We also introduce a variety of special cases of these grammars and establish their generative power. In the conclusion, we put all the achieved results into the context of formal language theory as a whole and formulate several open questions. Show more

Keywords: Regulated rewriting, ET0L grammars, random context, left variants, generative power, language families

DOI: 10.3233/FI-2013-811

Citation: Fundamenta Informaticae, vol. 123, no. 3, pp. 289-304, 2013

Authors: Moniri, Morteza

Article Type: Research Article

Abstract: First we define a new class of fuzzy Turing machines that we call Generalized Fuzzy Turing Machines. Our machines are equipped with rejecting states as well as accepting states. While we use a t-norm for computing degrees of accepting or rejecting paths, we use its dual t-conorm for computing the accepting or rejecting degrees of inputs. We naturally define when a generalized fuzzy Turing machine accepts or decides a fuzzy language. We prove that a fuzzy language L is decidable if and only if L and its complement are acceptable. Moreover, to each r.e. or co-r.e language L, we naturally …correspond a fuzzy language which is acceptable by a generalized fuzzy Turing machine. A converse to this result is also proved. We also consider Atanasov's intuitionistic fuzzy languages and introduce a version of fuzzy Turing machine for studying their computability theoretic properties. Show more

Keywords: Theory of Computing, Fuzzy Language, Fuzzy Turing Machine, Generalized Fuzzy Turing Machine, Intuitionistic Fuzzy Turing Machine

DOI: 10.3233/FI-2013-812

Citation: Fundamenta Informaticae, vol. 123, no. 3, pp. 305-315, 2013

Authors: Mróz, Andrzej

Article Type: Research Article

Abstract: We study the complexity of Bongartz's algorithm for determining a maximal common direct summand of a pair of modules M, N over k-algebra Λ; in particular, we estimate its pessimistic computational complexity 𝒪(rm6 n2 (n + m log n)), where m = dimk M ≤ n = dimk N and r is a number of common indecomposable direct summands of M and N. We improve the algorithm to another one of complexity 𝒪(rm4 n2 (n+m log m)) and we show that it applies to the isomorphism problem (having at least an exponential complexity in a direct approach). Moreover, we discuss …a performance of both algorithms in practice and show that the “average” complexity is much lower, especially for the improved one (which becomes a part of QPA package for GAP computer algebra system). Show more

Keywords: algorithm, computational complexity, computer algebra, GAP, module, common direct summand, Gaussian elimination, decomposition, isomorphism problem

DOI: 10.3233/FI-2013-813

Citation: Fundamenta Informaticae, vol. 123, no. 3, pp. 317-329, 2013

Authors: Simiński, Krzysztof

Article Type: Research Article

Abstract: The paper presents the clustering algorithm for data with missing values. In this approach both marginalisation and imputation are applied. The result of the clustering is the type-2 fuzzy set / rough fuzzy set. This approach enables the distinction between original and imputed data. The method can be applied to the data sets with all attributes lacking some values. The paper is accompanied by the numerical examples of clustering of synthetic and real-life data sets.

Keywords: missing values, clustering

DOI: 10.3233/FI-2013-814

Citation: Fundamenta Informaticae, vol. 123, no. 3, pp. 331-350, 2013

Authors: Wang, Changzhong | Chen, Degang | He, Qiang | Hu, Qinhua

Article Type: Research Article

Abstract: Covering information systems and ordered information systems are two important types of information systems. In this paper the relationships between covering information systems and ordered information systems are first examined, and it is proved that these two types of information systems are isomorphic under given conditions and can be equivalently transformed into each other. Then, the approach to attribute reduction in ordered information systems is proposed. Based on the isomorphism and equivalence of transformation, the method of attribute reduction in a covering information system can be directly obtained according to the reduction approach in an ordered information system. A practical …example is employed to show that the proposed method is an effective technique to deal with complex data sets. Show more

Keywords: Information systems, coverings, dominance relations, rough sets, attribute reduction

DOI: 10.3233/FI-2012-815

Citation: Fundamenta Informaticae, vol. 123, no. 3, pp. 351-363, 2013

Authors: Yang, Xibei | Qian, Yuhua | Yang, Jingyu

Article Type: Research Article

Abstract: Hierarchy plays a crucial role in the development of the granular computing. In this paper, three different hierarchies are considered for judging whether a granulation structure is finer or coarser than another one. The first hierarchy is based on the set containment of information granulations, the second hierarchy is based on the cardinal numbers of information granulations while the third hierarchy is based on the sum of cardinal numbers of information granulations. Through introducing set distance and knowledge distance, we investigate the algebraic lattices, in which the derived partial orders are corresponding to the three different hierarchies, respectively. From the …viewpoint of distance, these results look forward to provide a more comprehensible perspective for the study of hierarchies on granulation structures. Show more

Keywords: granular computing, granulation structure, hierarchy, knowledge distance, lattice, set distance

DOI: 10.3233/FI-2012-816

Citation: Fundamenta Informaticae, vol. 123, no. 3, pp. 365-380, 2013