Fundamenta Informaticae - Volume 139, issue 4

Authors: Eberbach, Eugene

Article Type: Research Article

Abstract: In the paper we define the class of hypercomputation complete and hard undecidable problems. We prove that typical unsolvable problems are decidable in infinity. We hypothesize that all undecidable problems can be reduced in infinity to each other, i.e., they are ℋ-complete (hypercomputation complete). We propose also two other classes: 𝒰-complete (universal complete) and 𝒟-complete (diagonalization complete) that use asymptotic reduction and allow separate non- RE and RE non-recursive undecidable classes.

Keywords: problem solving, hypercomputation, $-calculus, undecidability, p-decidability, e-decidability, a-decidability, i-decidability, ℋ-completeness, 𝒰-completeness, 𝒟-completeness

DOI: 10.3233/FI-2015-1237

Citation: Fundamenta Informaticae, vol. 139, no. 4, pp. 329-346, 2015

Authors: Gąsiorek, Marcin | Zając, Katarzyna

Article Type: Research Article

Abstract: Following the Coxeter spectral analysis of loop-free edge-bipartite graphs Δ and finite posets I , with n ≥ 2 vertices, introduced and developed in [SIAM J. Discrete Math., 27(2013), 827-854], we present a Coxeter spectral classification of finite posets I , with n ≥ 2 elements. Here we study the connected posets I that are non-negative of corank one or two, in the sense that the symmetric Gram matrix 1 2 ( C I + C I t r ) ∈ 𝕄 n ( ℚ ) is positive semi-definite …of corank one or two, where CI ∈ 𝕄n (ℤ) is the incidence matrix of I . We study such posets I by means of the Dynkin type Dyn I and the Coxeter polynomial coxI (t ) := det(t · E − CoxI ) ∈ ℤ[t ], where CoxI := −CI · C−tr I ∈ 𝕄n (ℤ) is the Coxeter matrix of I . Among other results, we develop an algorithmic technique that allows us to compute a complete list of such posets I , with |I | ≤ 16, their Dynkin types Dyn I , and the Coxeter polynomials coxI (t ) ∈ ℤ[t ]. We prove that, given a pair of such connected posets I and J , the incidence matrices CI and CJ are ℤ-congruent if and only if coxI (t ) = coxJ (t ) and Dyn I = Dyn J . Show more

Keywords: poset, Coxeter spectrum, Dynkin diagram, Coxeter-Dynkin type

DOI: 10.3233/FI-2015-1238

Citation: Fundamenta Informaticae, vol. 139, no. 4, pp. 347-367, 2015

Authors: Jezequel, Loïg | Fabre, Eric

Article Type: Research Article

Abstract: This paper proposes an approach to solve cost-optimal factored planning problems. Planning consists in organizing actions in order to reach some predefined goal. In factored planning one considers several interacting planning problems and has to design an action plan for each of them. But one must also guarantee that all these local plans are compatible: actions shared among several problems must be jointly performed or jointly rejected. We enrich the problem with the extra requirement that the global plan computed in this modular manner must also minimize the sum of all action costs. A solution is provided to this problem, …based on classical message passing algorithms, known as belief propagation in the setting of Bayesian networks. Here, messages carry complex information under the form of weighted (or (min; +)) automata, and all computations are performed with these objects. At the time our first paper on this topic was published, this method was the only one to solve cost-optimal factored planning problems in a modular way. Since then, new approaches were proposed. Experiments on classical benchmarks show that it is a valuable alternative to existing methods. Show more

Keywords: Factored planning, weighted automata, networks of automata, concurrency

DOI: 10.3233/FI-2015-1239

Citation: Fundamenta Informaticae, vol. 139, no. 4, pp. 369-401, 2015

Authors: Kułakowski, Konrad

Article Type: Research Article

Abstract: The pairwise comparisons method can be used when the relative order of preferences among different concepts (alternatives) needs to be determined. There are several popular implementations of this method, including the Eigenvector Method , the Least Squares Method , the Chi Squares Method and others. Each of the above methods comes with one or more inconsistency indices that help to decide whether the consistency of input guarantees obtaining a reliable output, thus taking the optimal decision. This article explores the relationship between inconsistency of input and error of output. An error describes to what extent the obtained results …correspond to the single expert’s assessments. On the basis of the inconsistency and the error, two properties of the weight deriving procedure are formulated. These properties are proven for eigenvector method and Koczkodaj’s inconsistency index. Several estimates using Koczkodaj’s inconsistency index for a principal eigenvalue, Saaty’s inconsistency index and the Condition of Order Preservation are also provided. Show more

DOI: 10.3233/FI-2015-1240

Citation: Fundamenta Informaticae, vol. 139, no. 4, pp. 403-419, 2015

Authors: Zhu, Kai | Liu, Guilong | Feng, Yanbin

Article Type: Research Article

Abstract: This paper proposes two different covering reduction algorithms by means of Boolean matrices. We define a dual notion of product on Boolean matrices and establish the relationship between characteristic matrix of a covering and relational matrices of two covering-induced relations, i.e. the minimum and the maximum relations in a covering. This paper shows that relational matrices of minimum and maximum relations in a covering can be written as intersection and union of many “elementary” matrices and each “elementary” matrix is corresponding to one element in the covering, respectively. Finally, as an application of this result, we propose two types of …covering reduction algorithms. Show more

Keywords: Boolean matrix, Boolean coproduct, Covering-induced relation, Covering reduction, Rough set

DOI: 10.3233/FI-2015-1241

Citation: Fundamenta Informaticae, vol. 139, no. 4, pp. 421-433, 2015

Article Type: Other

Citation: Fundamenta Informaticae, vol. 139, no. 4, pp. 435-436, 2015