On decidability of the decomposability problem for finite theories

We consider the decomposability problem for elementary theories, i.e. the problem of deciding whether a theory has a nontrivial representation as a union of two (or several) theories in disjoint signatures. For finite universal Horn theories, we prove that the decomposability problem is $ \sum _1^0 $ \sum _1^0 -complete and, thus, undecidable. We also demonstrate that the decomposability problem is decidable for finite theories in signatures consisting only of monadic predicates and constants.     

On Markovian decision models with a finite skeleton

We present a class of countable state space Markovian decision models that can be investigated by means of an associated finite-state, finite-action reduced model which we call the skeleton. In particular, we obtain a turnpike theorem for the original model (Theorem 2 in Section 5) from a known turnpike theorem for the reduced finite model. For illustration, we present in detail an application of this approach to an inventory model (re-establishing a known turnpike result) and sketch analogous results for a cash-balance model and a growth model.

---

Zusammenfassung Wir führen eine Klasse von Markovschen Entscheidungsmodellen mit abzählbarem Zustandsraum ein, die mittels eines verbundenen, reduzierten Modells mit endlichem Zustands- und Aktionsraum, welches wir das Skelett nennen, untersucht werden können. Insbesondere erhalten wir ein Turnpike Theorem für das ursprüngliche Modell (Theorem 2 im Abschnitt 5) von einem bekannten Turnpike Theorem für das reduzierte endliche Modell. Zur Erläuterung stellen wir im einzelnen eine Anwendung dieses Ansatzes für ein Lagerhaltungsmodell (Wiederherleitung eines bekannten Turnpike Ergebnisses) dar, und wir skizzieren analoge Ergebnisse für ein Kassenhaltungsmodell und ein Wachstumsmodell.

     

On the number of countable models of complete theories with finite Rudin-Keisler preorders

The aim of this article is to generalize the classification of complete theories with finitely many countable models with respect to two principal characteristics, Rudin-Keisler preorders and the distribution functions of the number of limit models, to an arbitrary case with a finite Rudin-Keisler preorder. We establish that the same characteristics play a crucial role in the case we consider. We prove the compatibility of arbitrary finite Rudin-Keisler preorders with arbitrary distribution functions f satisfying the condition rang f?ω∪{ω, 2^ω}.     

The problem of finite axiomatizability for strongly minimal graph theories

Translated from Algebra i Logika, Vol. 28, No. 3, pp. 280–297, May–June, 1989.     

On changing highest weight theories for finite W-algebras

A highest weight theory for a finite W-algebra $U(\mathfrak{g},e)$ was developed in Brundan et al. (Int. Math. Res. Not. 15:rnn051, 2008). This leads to a strategy for classifying the irreducible finite dimensional $U(\mathfrak{g},e)$ -modules. The highest weight theory depends on the choice of a parabolic subalgebra of $\mathfrak{g}$ leading to different parameterizations of the finite dimensional irreducible $U(\mathfrak{g},e)$ -modules. We explain how to construct an isomorphism preserving bijection between the parameterizing sets for different choices of parabolic subalgebra when $\mathfrak{g}$ is of type A, or when $\mathfrak{g}$ is of types C or D and e is an even multiplicity nilpotent element.     

Reduced sub-powers and the decision problem for finite algebras in arithmetical varieties

The aim of this paper is to prove that every finitely generated, arithmetical variety of finite type, in which every subdirectly irreducible algebra has linearly ordered congruences has a decidable first order theory of its finite members. The proof is based on a representation of finite algebras from such varieties by some quotients of special subdirect products in which sets of indices are partially ordered into dual trees. Then the result of M. O. Rabin about decidability of the monadic second order theory of two successors is applied.Presented by Stanley Burris.     

On the subset sum problem for finite fields

Let G be the additive group of a finite field. J. Li and D. Wan determined the exact number of solutions of the subset sum problem over G, by giving an explicit formula for the number of subsets of G of prescribed size whose elements sum up to a given element of G. They also determined a closed-form expression for the case where the subsets are required to contain only nonzero elements. In this paper we give an alternative proof of the two formulas. Our argument is purely combinatorial, as in the original proof by Li and Wan, but follows a different and somehow more “natural” approach. We also indicate some new connections with coding theory and combinatorial designs.     

On finite element methods for the Neumann problem

Summary The Neumann problem for a second order elliptic equation with self-adjoint operator is considered, the unique solution of which is determined from projection onto unity. Two variational formulations of this problem are studied, which have a unique solution in the whole space. Discretization is done via the finite element method based on the Ritz process, and it is proved that the discrete solutions converge to one of the solutions of the continuous problem. Comparison of the two methods is done.     

The decision problem for some logics for finite words on infinite alphabets

This paper is a follow-up to a previous paper where the logical characterization of n-ary synchronous relations due to Eilenbeig, Elgot, and Shepherdson was investigated in the case where the alphabet has infinitely many letters. Here we show that modifying one of the predicates leads to a completely different picture for infinite alphabets, though it does not change the expressive power for finite alphabets. Indeed, roughly speaking, being able to express the fact that two words end with the same symbol leads to an undecidable theory, already for the Σ₂ fragment. Finally, we show that the existential fragment is decidable. Bibliography: 19 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 358, 2008, pp. 100–119.     

On the optimality of algorithms for finite state sequential decision processes

A finite state sequential decision process (sdp) is a model which is able to represent a wide variety of combinatorial optimization problems. Four known and two new algorithms for obtaining optimal policies of three subclasses of sdp's, r-lmsdp, r-pmsdp, and r-psmsdp, are considered, and their optimality in the sense of minimizing the number of evaluations of cost functions associated with state transitions is proved.     

On the isomorphism problem for finite dimensional diagram algebras

somorphism problems for finite dimensional algebras can be computationally hard. When the algebras are monomial, it is shown, refining work of Shirayanagi, that there is a simple definitive combinatorial method. However, examples show that no such criterion is possible if the class of algebras is expanded to that of diagram algebras (in the sense of Fuller). The presentation of a diagram algebra is field independent but the existence of an isomorphism between two such is not. (Subject classes: 16G30, 16P10, 20M25).     

On the solution of the finite moment problem

In this work we propose a method to obtain the normal solution of the finite moment problem both in the absence and in the presence of linear boundary constraints. The method gives the normal solution as a linear combination of Jacobi polynomials and furnishes its coefficients in terms of the moments. A number of examples are given to illustrate the strength of the method.     

On stability in finite models

We search for a set-up in which results from the theory of infinite models hold for finite models. As an example we prove results from stability theory. Received: 23 February 1998     

On the finite basis problem for certain 2-limited words

Let X* be a free monoid over an alphabet X and W be a finite language over X. Let S(W) be the Rees quotient X*/I(W), where I(W) is the ideal of X* consisting of all elements of X* that are not subwords of W. Then S(W) is a finite monoid with zero and is called the discrete syntactic monoid of W. W is called finitely based if the monoid S(W) is finitely based. In this paper, we give some sufficient conditions for a monoid to be non-finitely based. Using these conditions and other results, we describe all finitely based 2-limited words over a three-element alphabet. Furthermore, an explicit algorithm is given to decide that whether or not a 2-limited word in which there are exactly two non-linear letters is finitely based.     

On finite element schemes of the dirichlet problem

In this paper, we consider finite element schemes applied to the Dirichlet problem for the system of nonlinear elliptic equations, based on piecewise linear polynomials, and present iterative methods for solving algebraic nonlinear equations, which construct monotone sequences. Furthermore, we derive error estimates which imply uniform convergence. Our results are based on the discrete maximum principle. Finally, some typical numerical examples are given to demonstrate the usefulness of convergence results.