Fundamenta Informaticae - Volume 152, issue 3

Authors: El Kholy, Warda | Bentahar, Jamal | El Menshawy, Mohamed | Qu, Hongyang | Dssouli, Rachida

Article Type: Research Article

Abstract: Social approaches have been put forward to define semantics for intelligent agent communication messages and to tackle the shortcomings of mental approaches. Formal semantics of those social approaches can be model checked as they are focused on public behaviors instead of private mental states. Social conditional commitments are essential concepts in social approaches that can effectively model agent communications. However, conditional commitments exclusively are not able to model agent communication actions, the cornerstone of the fundamental agent communication theory, namely speech act theory . These actions provide mechanisms for dynamic interactions and enable designers to track the evolution of active …conditional commitments. From the perspective of model checking, we need to define a formal and computationally grounded semantics for relevant social actions that can directly be applied to active conditional commitments. This manuscript describes a new symbolic model checker, SMC4AC, developed and implemented to automate the verification of interaction among intelligent agents. SMC4AC is the result of developing a new symbolic model checking algorithm devoted to CTLCα , a combination of CTL and new temporal modalities to represent and reason about conditional commitments and common commitment actions. The core of this paper consists of a new logical language, a detailed description of the symbolic algorithms needed for commitments and their action modalities, complexity analysis, implementation and application. The implementation of our algorithm and its graphical user interface is built on top of the MCMAS symbolic model checker tailored for checking intelligent multi-agent systems. We select business processes and multi-agent interaction protocols as application domains to test and validate the effectiveness and scalability of SMC4AC. We report extensive experimental results, which confirm the theoretical findings and make SMC4AC practical. Show more

Keywords: Symbolic model checker, conditional commitment, conditional commitment actions, expressiveness, commitment action modalities, verification

DOI: 10.3233/FI-2017-1519

Citation: Fundamenta Informaticae, vol. 152, no. 3, pp. 223-271, 2017

Authors: Lemańska, Magdalena | Rodríguez-Velázquez, Juan Alberto | Trujillo-Rasua, Rolando

Article Type: Research Article

Abstract: A vertex cover of a graph G = (V , E ) is a set X ⊂ V such that each edge of G is incident to at least one vertex of X . The vertex cover number τ (G ) is the minimum cardinality of a vertex cover of G . A dominating set D ⊆ V is a weakly connected dominating set of G if the subgraph G [D ]w = (N [D ], E w ) weakly induced by D , is connected, where Ew …is the set of all edges having at least one vertex in D . The weakly connected domination number γw (G ) of G is the minimum cardinality among all weakly connected dominating sets of G . In this article we characterize the graphs where γw (G ) = τ (G ). In particular, we focus our attention on bipartite graphs, regular graphs, unicyclic graphs, block graphs and corona graphs. Show more

Keywords: Vertex cover number, weakly connected domination number

DOI: 10.3233/FI-2017-1520

Citation: Fundamenta Informaticae, vol. 152, no. 3, pp. 273-287, 2017

Authors: Pomykała, Jacek

Article Type: Research Article

Abstract: In the paper we prove that all but at most x/A(x) positive integers n ≤ x can be completely factored in deterministic polynomial time C(x), querying the prime decomposition exponent oracle at most D(x) times. The functions A(x), C(x) and D(x) have the polynomial growth (of log x ) at infinity.

Keywords: Brun-Titchmarsh inequality, factoring algorithms, Zn*-generating sets, Dirichlet characters, smooth numbers, Discrete Logarithm Problem for Composite Numbers

DOI: 10.3233/FI-2017-1521

Citation: Fundamenta Informaticae, vol. 152, no. 3, pp. 289-295, 2017

Authors: Yang, Yong | Peng, Xindong

Article Type: Research Article

Abstract: Soft set theory was originally proposed by Molodtsov in 1999 as a general mathematical tool for dealing with uncertainty. However, it has been pointed out that classical soft set model is not appropriate to deal with imprecise and fuzzy problems. In order to handle these types of problems, some fuzzy extensions of soft set theory are presented, yielding fuzzy soft set theory. As a further research, in this work, we first propose concepts of interval fuzzy sets and interval fuzzy soft sets, define some operations on them and study some of their relevant properties, especially, the dual laws are discussed …with respect to difference operation in interval fuzzy soft set theory. We then introduce a revised Technique for Order Preference by Similarity to an Ideal Solution (TOPSIS) method and choice value method for interval fuzzy soft set which the weight information is completely unknown. Meanwhile, an analysis of computation complexity is employed, also the discriminative power of two methods are shown. Finally, two illustrative examples are employed to show that they can be successfully applied to problems that contain uncertainties. Show more

Keywords: Interval fuzzy sets, interval fuzzy soft sets, TOPSIS, computation complexity, discriminative power

DOI: 10.3233/FI-2017-1522

Citation: Fundamenta Informaticae, vol. 152, no. 3, pp. 297-321, 2017