On distributive fixed-point expressions
On Distributive Fixed-Point Expressions
For every fixed-point expression e of alternation-depth r, we construct a new fixed-point expression e' of alternation-depth 2 and size . Expression e' is equivalent to e whenever operators are distributive and the underlying complete lattice has a co-continuous least upper bound. We alternation-depth but also w.r.t. the increase in size of the resulting expression.
On dot-depth two
On existentially first-order definable languages and their relation to NP
On Existentially First-Order Definable Languages and Their Relation to NP
Under the assumption that the Polynomial-Time Hierarchy does not collapse we show for a regular language L: the unbalanced polynomial-time leaf language class determined by L equals iff L is existentially but not quantifierfree definable in FO[<, min, max, +1, −1]. Furthermore, no such class lies properly between NP and co-1-NP or NP⊕co-NP. The proofs rely on a result of Pin and Weil characterizing the automata of existentially first-order definable languages.
On extremum-searching approximate probabilistic algorithms
On free pseudo-complemented and relatively pseudo-complemented semi-lattices
On generalizations of a theorem on recursive sets
On interpretability in set theories. II.
On interpretability in theories containing arithmetic
On L 1 Space Formed by Complex-Valued Partial Functions
In this article, we formalized L1 space formed by complexvalued partial functions [11], [15]. The real-valued case was formalized in [22] and this article is its generalization.
On L 1 Space Formed by Real-Valued Partial Functions
This article contains some definitions and properties refering to function spaces formed by partial functions defined over a measurable space. We formalized a function space, the so-called L1 space and proved that the space turns out to be a normed space. The formalization of a real function space was given in [16]. The set of all function forms additive group. Here addition is defined by point-wise addition of two functions. However it is not true for partial functions. The set of partial functions...
On L p Space Formed by Real-Valued Partial Functions
This article is the continuation of [31]. We define the set of Lp integrable functions - the set of all partial functions whose absolute value raised to the p-th power is integrable. We show that Lp integrable functions form the Lp space. We also prove Minkowski's inequality, Hölder's inequality and that Lp space is Banach space ([15], [27]).
On Markov Properties Of Finitely Presented Groups
On Markov properties of finitely presented groups.
On minimal pairs and minimal degrees in higher recursion theory.
On nonmonotone inductive definability
On problems of databases over a fixed infinite universe
In the relational model of databases a database state is thought of as a finite collection of relations between elements. For many applications it is convenient to pre-fix an infinite domain where the finite relations are going to be defined. Often, we also fix a set of domain functions and/or relations. These functions/relations are infinite by their nature. Some special problems arise if we use such an approach. In the paper we discuss some of the problems. We show that there exists a recursive...
On pseudo-random sequences and their relation to a class of stochastical laws
On rational solution of the state equation of a finite automaton.