Fundamenta Informaticae

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.

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 C_I ∈ 𝕄 _n (ℤ) is the incidence matrix of I. We study such posets I by means of the Dynkin type Dyn _I and the Coxeter polynomial cox _I (t) := det(t · E − Cox _I ) ∈ ℤ[t], where Cox _I := −C_I · 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 cox _I (t) ∈ ℤ[t]. We prove that, given a pair of such connected posets I and J, the incidence matrices C_I and C_J are ℤ-congruent if and only if cox _I (t) = cox _J (t) and Dyn _I = Dyn _J .

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.

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.

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.