稳定完备婚姻问题的算法及推广

稳定匹配问题是算法理论中的典型问题之一,稳定婚姻匹配问题则是一种解决二部图匹配问题的模型.论文对稳定婚姻匹配问题进行了简单的阐述,并介绍了求解典型稳定婚姻问题的Gale-Shapley算法的基本思想及其性质,并且再推广到广义的延迟认可算法,解决现实生活中的公司招聘员工等的案例.     

On extension of the maximin problem

Consideration was given to an abstract version of the program maximin problem with constraints of the pulse and moment nature. The “moment” constraints were relaxed, and the asymptotics of the realized values of maximin in the problems with relaxed constraints was studied together with its representation in the class of generalized elements (controls) defined as finite-additive measures. In particular, the questions of universal “within the given range” representation of the above asymptotics were investigated.     

A semantically complete extension sequence of the system (?)

In this paper, the method of well-combined semantics and syntax proposed by Pavelka is applied to the research of the prepositional calculus formal system (?)*. The partial constant values are taken as formulas, formulas are fuzzified in two manners of semantics and syntax, and inferring processes are fuzzified. A sequence of new extensions {(?)_n~*} of the system ? is proposed, and the completeness of (?)_n~* is proved.     

A semantically complete extension sequence of the system L

In this paper, the method of well-combined semantics and syntax proposed by Pavelka is applied to the research of the propositional calculus formal system L*. The partial constant values are taken as formulas, formulas are fuzzified in two manners of semantics and syntax, and inferring processes are fuzzified. A sequence of new extensions {Ln*} of the system L* is proposed, and the completeness of Ln* is proved.     

The complete realization problem for hidden Markov models: a survey and some new results

Suppose m is a positive integer, and let ${\mathcal{M} = \{1, \ldots ,m\}}$ . Suppose ${\{\mathcal{Y}_t \}}$ is a stationary stochastic process assuming values in ${\mathcal{M}}$ . In this paper we study the question: When does there exist a hidden Markov model (HMM) that reproduces the statistics of this process? This question is more than forty years old, and as yet no complete solution is available. In this paper, we begin by surveying several known results, and then we present some new results that provide ??almost?? necessary and sufficient conditions for the existence of a HMM for a mixing and ultra-mixing process (where the notion of ultra-mixing is introduced here). In the survey part of the paper, consisting of Sects. 2 through 8, we rederive the following known results: (i) Associate an infinite matrix H with the process, and call it a ??Hankel?? matrix (because of some superficial similarity to a Hankel matrix). Then the process has a HMM realization only if H has finite rank. (ii) However, the finite Hankel rank condition is not sufficient in general. There exist processes with finite Hankel rank that do not admit a HMM realization. (iii) An abstract necessary and sufficient condition states that a frequency distribution has a realization as an HMM if and only if it belongs to a ??stable polyhedral?? convex set within the set of all frequency distributions on ${\mathcal{M}^{*}}$ , the set of all finite strings over ${\mathcal{M}}$ . While this condition may be ??necessary and sufficient,?? it virtually amounts to a restatement of the problem rather than a solution of it, as observed by Anderson (Math Control Signals Syst 12(1):80?C120, 1999). (iv) Suppose a process has finite Hankel rank, say r. Then there always exists a ??regular quasi-realization?? of the process. That is, there exist a row vector, a column vector, and a set of matrices, each of dimension r or r ×?r as appropriate, such that the frequency of arbitrary strings is given by a formula that is similar to the corresponding formula for HMM??s. Moreover, all quasi-regular realizations of the process can be obtained from one of them via a similarity transformation. Hence, given a finite Hankel-rank process, it is a simple matter to determine whether or not it has a regular HMM in the conventional sense, by testing the feasibility of a linear programming problem. (v) If in addition the process is ??-mixing, every regular quasi-realization has additional features. Specifically, a matrix associated with the quasi-realization (which plays the role of the state transition matrix in a HMM) is ??quasi-row stochastic?? (in that its rows add up to one, even though the matrix may not be nonnegative), and it also satisfies the ??quasi-strong Perron property?? (its spectral radius is one, the spectral radius is a simple eigenvalue, and there are no other eigenvalues on the unit circle). A corollary is that if a finite Hankel rank ??-mixing process has a regular HMM in the conventional sense, then the associated Markov chain is irreducible and aperiodic. While this last result is not surprising, it does not seem to have been stated explicitly. While the above results are all ??known,?? they are scattered over the literature; moreover, the presentation here is unified and occasionally consists of relatively simpler proofs than are found in the literature. Next we move on to present some new results. The key is the introduction of a property called ??ultra-mixing.?? The following results are established: (a) Suppose a process has finite Hankel rank, is both ??-mixing as well as ??ultra-mixing,?? and in addition satisfies a technical condition. Then it has an irreducible HMM realization (and not just a quasi-realization). Moreover, the Markov process underlying the HMM is either aperiodic (and is thus ??-mixing), or else satisfies a ??consistency condition.?? (b) In the other direction, suppose a HMM satisfies the consistency condition plus another technical condition. Then the associated output process has finite Hankel rank, is ??-mixing and is also ultra-mixing. Moreover, it is shown that under a natural topology on the set of HMMs, both ??technical?? conditions are indeed satisfied by an open dense set of HMMs. Taken together, these two results show that, modulo two technical conditions, the finite Hankel rank condition, ??-mixing, and ultra-mixing are ??almost?? necessary and sufficient for a process to have an irreducible and aperiodic HMM.     

On the complete controllability indexes assignment problem

New solvability conditions for the simultaneous assignment by static-state feedback of both the controllability indexes of (A, B) and the invariant factors of (sI-A, -B) are given. These conditions enhance the fact that this problem is a generalization of the control structure problem of Rosenbrock (1970) and of the controllability indexes assignment problem of Heymann (1981). The choice of a polynomial framework allows one to obtain simpler proofs of the results than those previously published     

An extension to the single bottleneck transportation problem

In the existing models of bottleneck transportation problem (BTP), the transport time along a given path is taken as a fixed charge. In most practical situations, however, the transport time usually varies with the amount of transport. In order to make up this defect, an extended BTP model is built in which transport time t_ij is determined by a function of the amount to be transported rather than a constant. A heuristic recursive algorithm is proposed for the solution of the model. Furthermore, a special case of the model (that the supplies at sources are sufficient) is studied and a set of formulae of optimal solution are derived.     

Replica management for fault-tolerant systems

Replication has traditionally been used to assure fault tolerance. Active parallel replication is a new technique that, in addition to ensuring fault tolerance, dramatically reduces computation time and cost     

An extension of the stochastic linear regulator problem

The stochastic linear regulator problem is extended to cover the case of non-Gaussian white noise. Using martingale theory, it is proved that the linear optimal regulator is also optimal for non-Gaussian white noise.     

The problem of determining the size of a complete set of reductions

This article is the tenth of a series of articles discussing various open research problems in automated reasoning. Here we focus on finding criteria for accurately predicting the size of a complete set of reductions when such a set exists. We include a suggestion for evaluating a proposed solution to this research problem.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

The problem of guaranteeing the existence of a complete set of reductions

This article is the eleventh of a series of articles discussing various open research problems in automated reasoning. Here we focus on finding criteria for guaranteeing the existence of a complete set of reductions. We include a suggestion for evaluating a proposed solution to this research problem.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

The problem of guaranteeing the absence of a complete set of reductions

This article is the twelfth of a series of articles discussing various open research problems in automated reasoning. Here we focus on finding criteria for guaranteeing the absence of a complete set of reductions. We include a suggestion for evaluating a proposed solution to this research problem.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

The duality of fault-tolerant system structures

An examination of the structure of fault-tolerant systems incorporating backward error recovery indicates a partitioning into two broad classes. Two canonical models, each representing a particular class of systems, have been constructed. The first model incorporates objects and actions as the entities for program construction whereas the second model employs communicating processes and conversations. Applications in areas such as office information and banking systems are typically described and built in terms of the first model whereas applications in the area of process control are usually described and built in terms of the second model. The paper claims that the two models are duals of each other and presents arguments and examples to substantiate this claim. It will be shown that the techniques that have been developed within the context of one model turn out to have interesting and hitherto unexplored duals in the other model.     

The Researches in Fault-Tolerant D ataflow Architecture

Fault-tolerant dataflow system is an entirely new field.This paper presents an overview of FTDF-TD,a fault-tolerant dataflow system.Various aspects of FTDF-TD,such as the architecture,the fault-tolerant strategy,and its reliability,are described.The research on overhead and performance evaluation based on software simulation is introduced.It is shown that FTDF-TD gets valuable results in reducing overhead,execution time and increasing reliability of processor array,compared with two other fault-tolerant systems.     

Systematic formal verification for fault-tolerant time-triggeredalgorithms

Many critical real-time applications are implemented as time-triggered systems. We present a systematic way to derive such time-triggered implementations from algorithms specified as functional programs (in which form their correctness and fault-tolerance properties can be formally and mechanically verified with relative ease). The functional program is first transformed into an untimed synchronous system and, then, to its time-triggered implementation. The first step is specific to the algorithm concerned, but the second is generic and we prove its correctness. This proof has been formalized and mechanically checked with the PVS verification system. The approach provides a methodology that can ease the formal specification and assurance of critical fault-tolerant systems     

A fault-tolerant protocol for atomic broadcast

A general protocol for atomic broadcast in networks is presented. The protocol tolerates loss, duplication, reordering, delay of messages, and network partitioning in an arbitrary network of fail-stop sites (i.e. no Byzantine site behavior is tolerated). The protocol is based on majority-concensus decisions to commit on unique ordering of received broadcast messages. Under normal operating conditions, the protocol requires three phases to complete and approximately 4N/V messages where N is the number of sites. This overhead is distributed among the messages of which the delivery decision is made and the heavier the broadcast message traffic, the lower the overhead per broadcast message becomes. Under abnormal operating conditions, a decentralized termination protocol (also presented) is invoked. A performance analysis of this protocol is presented, showing that this protocol commits with high probability under realistic operating conditions without invoking termination protocol if N is sufficiently large. The protocol retains its efficiency in wide-area networks where broadcast communication media are unavailable