On the structures of generating iterated function systems of Cantor sets

A generating IFS of a Cantor set F is an IFS whose attractor is F. For a given Cantor set such as the middle-3rd Cantor set we consider the set of its generating IFSs. We examine the existence of a minimal generating IFS, i.e. every other generating IFS of F is an iterating of that IFS. We also study the structures of the semi-group of homogeneous generating IFSs of a Cantor set F in under the open set condition (OSC). If dim_HF<1 we prove that all generating IFSs of the set must have logarithmically commensurable contraction factors. From this Logarithmic Commensurability Theorem we derive a structure theorem for the semi-group of generating IFSs of F under the OSC. We also examine the impact of geometry on the structures of the semi-groups. Several examples will be given to illustrate the difficulty of the problem we study.     

Reducibility on families

A reducibility on families of subsets of natural numbers is introduced which allows the family per se to be treated without its representation by natural numbers being fixed. This reducibility is used to study a series of problems both in classical computability and on admissible sets: for example, describing index sets of families belonging to , generalizing Friedberg’s completeness theorem for a suitable reducibility on admissible sets, etc. *Supported by RFBR (project No. 05-01-00605) and by the Council for Grants (under RF President) and State Aid of Young Candidates of Science (grant MK-4314.2008.1). **Supported by RFBR (projects No. 08-01-00442 and 06-04002-DFGa), by the Council for Grants (under RF President) of Leading Scientific Schools (grant NSh-335.2008.1), and by the Russian Foundation for Support of Domestic Science. Translated from Algebra i Logika, Vol. 48, No. 1, pp. 31-53, January-February, 2009.     

A constructive characterization of total domination vertex critical graphs

Let G be a graph of order n and maximum degree Δ(G) and let γ_t(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G−v is less than the total domination number of G. We call these graphs γ_t-critical. For any γ_t-critical graph G, it can be shown that n≤Δ(G)(γ_t(G)−1)+1. In this paper, we prove that: Let G be a connected γ_t-critical graph of order n (n≥3), then n=Δ(G)(γ_t(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.     

一类非单调二阶锥互补问题解集的非空性与有界性

本文在二阶锥上引入一类新的映射,称之为笛卡尔P_*(κ)映射,它是单调映射的推广.文中讨论涉及这类映射的二阶锥互补问题的解的存在性和解集的有界性.主要结论为:如果所考虑的互补问题是严格可行的,那么它的解集是非空有界的.     

Partial regularity and singular sets of solutions of higher order parabolic systems

In the present paper we provide a broad survey of the regularity theory for non-differentiable higher order parabolic systems of the type

Scheduling of corrugated paper production

Corrugated paper is produced by gluing three types of papers of the same breadth. Given a set of orders, we first assign each order to one of the standard breadths, and then sequence those assigned to each standard breadth so that they are continuously manufactured from the three rolls of the specified standard breadth equipped in the machine called corrugator. Here we are asked to achieve multi-goals of minimizing total length of roll papers, total loss of papers caused by the differences between standard breadths and real breadths of the orders, and the number of machine stops needed during production. We use integer programming to assign orders to standard breadths, and then develop a special purpose algorithm to sequence the orders assigned to each standard breadth. This is a first attempt to handle scheduling problems of the corrugator machine.     

Rough set approach to multiple criteria classification with imprecise evaluations and assignments

Dominance-based Rough Set Approach (DRSA) has been introduced to deal with multiple criteria classification (also called multiple criteria sorting, or ordinal classification with monotonicity constraints), where assignments of objects may be inconsistent with respect to dominance principle. In this paper, we consider an extension of DRSA to the context of imprecise evaluations of objects on condition criteria and imprecise assignments of objects to decision classes. The imprecisions are given in the form of intervals of possible values. In order to solve the problem, we reformulate the dominance principle and introduce second-order rough approximations. The presented methodology preserves well-known properties of rough approximations, such as rough inclusion, complementarity, identity of boundaries and precisiation. Moreover, the meaning of the precisiation property is extended to the considered case. The paper presents also a way to reduce decision tables and to induce decision rules from rough approximations.     

Optimal risk probability for first passage models in semi-Markov decision processes

This paper studies the risk minimization problem in semi-Markov decision processes with denumerable states. The criterion to be optimized is the risk probability (or risk function) that a first passage time to some target set doesn't exceed a threshold value. We first characterize such risk functions and the corresponding optimal value function, and prove that the optimal value function satisfies the optimality equation by using a successive approximation technique. Then, we present some properties of optimal policies, and further give conditions for the existence of optimal policies. In addition, a value iteration algorithm and a policy improvement method for obtaining respectively the optimal value function and optimal policies are developed. Finally, two examples are given to illustrate the value iteration procedure and essential characterization of the risk function.