Fundamenta Informaticae - Volume 137, issue 4

Authors: Champarnaud, Jean-Marc | Dubernard, Jean-Philippe | Jeanne, Hadrien | Mignot, Ludovic

Article Type: Research Article

Abstract: The aim of this paper is to design a polynomial construction of a finite recognizer for hairpin completions of regular languages. This is achieved by considering completions as new expression operators and by applying derivation techniques to the associated extended expressions called hairpin expressions. More precisely, we extend partial derivation of regular expressions to two-sided partial derivation of hairpin expressions and we show how to deduce a recognizer for a hairpin expression from its two-sided derived term automaton, providing an alternative proof of the fact that hairpin completions of regular languages are linear context-free.

Keywords: Expression Derivatives, Hairpin Expression, Two-Sided Derivatives, Finite Recognizer

DOI: 10.3233/FI-2015-1189

Citation: Fundamenta Informaticae, vol. 137, no. 4, pp. 425-455, 2015

Authors: Gong, Zengtai | Zhang, Xiaoxia

Article Type: Research Article

Abstract: Fuzzy set theory, soft set theory and rough set theory are powerful mathematical tools for dealing with various types of uncertainty. This paper is devoted to define a broad family of soft fuzzy rough sets, each one of which, called an (I, J)-soft fuzzy rough set, is determined by a pair of border implicators (I, J). Alternatively, it shows that a fuzzy soft set can induce a T-equivalence fuzzy relation which is used to granulate the universe. In particular, we prove that (I, J)-fuzzy soft rough sets in our work are equivalent to (I, J)-fuzzy rough sets of Yao et …al. by using a T-equivalence fuzzy relation determined by a fuzzy soft set. Furthermore, basic properties of (I, J)-fuzzy soft rough sets are investigated. Meanwhile, an operator-oriented characterization of (I, J)-fuzzy soft rough sets is proposed. Finally, an example is given to illustrate the approach of present paper. Show more

Keywords: Fuzzy set, rough set, soft set, fuzzy soft set, fuzzy logical operation, (I, J)-soft fuzzy rough set, (I, J)-fuzzy rough set

DOI: 10.3233/FI-2015-1190

Citation: Fundamenta Informaticae, vol. 137, no. 4, pp. 457-491, 2015

Authors: Peters, Georg

Article Type: Research Article

Abstract: Since its introduction a prime area of application of rough sets theory has been in the field of classification. In this area rough sets theory provides a powerful toolbox of methods to deal with incomplete and contradicting information. Obviously, the assessment of the obtained classification results is of crucial importance. In our paper, we propose and evaluate some rough performance indices to evaluated the quality of bi- and multinomial classifiers. To illustrate their characteristics we perform comparative experiments on a synthetically generated data set.

Keywords: Rough Sets, Classification, Performance Indices, Boundary Roughness

DOI: 10.3233/FI-2015-1191

Citation: Fundamenta Informaticae, vol. 137, no. 4, pp. 493-515, 2015

Authors: Surynek, Pavel

Article Type: Research Article

Abstract: A parallel version of the problem of cooperative path-finding (pCPF) is introduced in this paper. The task in CPF is to determine a spatio-temporal plan for each member of a group of agents. Each agent is given its initial location in the environment and its task is to reach the given goal location. Agents must avoid obstacles and must not collide with one another. The environment where agents are moving is modeled as an undirected graph. Agents are placed in vertices and they move along edges. At most one agent is placed in each vertex and at least one vertex …remains unoccupied. An agent can only move into a currently unoccupied vertex in the standard version of CPF. In the parallel version, an agent can also move into a vertex being currently vacated by another agent supposing the character of this movement is not cyclic. The optimal pCPF where the task is to find the smallest possible solution of the makespan is particularly studied. The main contribution of this paper is the proof of NP-completeness of the decision version of the optimal pCPF. A reduction of propositional satisfiability (SAT) to the problem is used in the proof. Show more

Keywords: cooperative path-finding (CPF), parallelism, multi-agent, sliding puzzle, ($N^2$ - 1)-puzzle, N × N-puzzle, 15-puzzle, domain dependent planning, complexity, NP-completeness

DOI: 10.3233/FI-2015-1192

Citation: Fundamenta Informaticae, vol. 137, no. 4, pp. 517-548, 2015

Article Type: Other

Citation: Fundamenta Informaticae, vol. 137, no. 4, pp. 549-550, 2015