The equality problem for vector addition systems is undecidable

We demonstrate the usefulness of Petri nets for treating problems about vector addition systems by giving a simple exposition of Rabin's proof of the undecidability of the inclusion problem for vector addition system reachability sets, and then proceed to show that the inclusion problem can be reduced to the equality problem for reachability sets.     

Transient analysis of acyclic markov chains

Continuous-time Markov chains are commonly used insystem reliability modeling. In this paper, we discuss a method for automatically deriving transient solutions that are symbolic in t for acyclic Markov chains. Our method also includes parametric sensitivity analysis of the transient solution and several cumulative measures associated with Markov chain behavior. We include three examples, one to show the use of our method in evaluating approximate solution techniques, one showing parametric sensitivity analysis of a large Markov model, and one demonstrating the computation of cumulative measures for an acyclic Markov reward process.     

Computation of mutual entropy in quantum markov chains

There are several damping phenomena in quantum optics. Such phenomena have been usually explained by open systems. In statistical physics, open system dynamics have been used to study the irreversibility and the approach to equilibrium. In this paper, the dynamical change of the mutual entropy for an open system, frequently studied in the quantum optics literature, is rigorously computed through a model of quantum Markov chain. In particular, the concrete formula of Stinespring expression for such a model is obtained and applied to the derivation of the mutual entropy, and some computational results are presented.     

The 4-way deterministic tiling problem is undecidable

It is shown that the (infinite) tiling problem by Wang tiles is undecidable even if the given tile set is deterministic by all four corners, i.e. a tile is uniquely determined by the colors of any two adjacent edges. The reduction is done from the Turing machine halting problem and uses the aperiodic tile set of Kari and Papasoglu.     

On an undecidable problem related to difference equations with parameters

Linear difference equations with polynomial coefficients depending on parameters are considered. It is proved that the problem of existence of numerical values of parameters for which the given equation has a polynomial solution (alternatively, a solution given by a rational function) is undecidable (similar to the undecidability of the same problem in the differential case proved by J.-A. Weil).     

Increasing recommended effectiveness with markov chains and purchase intervals

Recommendation system is an important component of many websites and has brought huge economic benefits and challenges for online shoppers and e-commerce companies. Existing recommendation systems focus on producing a list of products which users may be interested to purchase, while overlooking the purchase chain and temporal diversity which may increase the likelihood of a purchase decision. In this paper, we propose to utilize the Markov chain to track the chain of users’ purchase behaviors and utilize the purchase intervals to improve the temporal diversity for e-commerce recommender. We design and implement several algorithms and integrate these into our recommendation model. We evaluate our system on a real-world e-commerce dataset. Experimental results demonstrate that our approach significantly improves the accuracy, conversion rate and temporal diversity compared to the state-of-the-art algorithms.     

An undecidable property of context-free linear orders

We prove that there exists no algorithm to decide whether the language generated by a context-free grammar is dense with respect to the lexicographic ordering. As a corollary to this result, we show that it is undecidable whether the lexicographic orderings of the languages generated by two context-free grammars have the same order type.     

Optimal control of markov chains admitting strong and weak interactions

This paper is devoted to the study of an optimal control problem for a Markov chain with generator B + εA, where ε is a small parameter. It is shown that an approximate solution can be calculated by a policy improvement algorithm involving computations relative to an ‘aggregated’ problem (the dimension of which is given by N, the number of ergodic sets for the B matrix) together with a family of ‘decentralized’ problems (the dimensions of which are given by the number of elements in each ergodic set for the B matrix).     

An adaptive automaton controller for discrete-time markov processes

The computation of an optimal feedback controller characteristic for a non-linear stochastic system may be facilitated by the use of a stochastic automaton as a system model. A problem of particular interest is that of a long duration stationary Markov process in which the state is observable but the process dynamics and disturbance characteristics are initially unknown. The determination of a suitable control algorithm, in the form of an adaptive automation in the feedback loop, is considered in this paper for such a process.

Since the algorithm is to be used on-line to perform simultaneously the functions of estimation and control, it must constitute an efficient convergent multi-stage dual control strategy. It is shown that an existing method for dual control of a repetitive single-stage stochastic process may be extended to apply to the present case. A method is introduced of calculating successive policy estimates recursively, so that the task of updating the estimated optimal feedback policy at each stage of the process is rendered feasible. The application of the automaton controller is illustrated by the simulated adaptive control of a non-linear conditionally stable heat treatment process disturbed by multiplicative noise.     

The analysis of academic retrenchment using parametric programming and markov chains

This paper, recognizing that retrenchment is the prognosis for the forseeable future for most collegiate institutions, employs Markov chains to trace the passage of faculty in time, and linear and parametric programming to provide guidelines for control of faculty size and composition. If cutbacks in size need to be carried out, how best should this be done? How does affirmative action influence the decision? What about accrediting agency regulations? What effects on quality can be anticipated? What policies should be recognized simultaneously? These and other questions are examined on both short-run and long-run bases using aggregated variables and a very detailed illustration.     

Optimal and near-optimal incentive strategies in the hierarchical control of markov chains

This paper considers Markovian Stackelberg problems with one leader and N followers. Firstly, an algorithm is proposed to compute optimal affine incentive strategy for the leader and Nash reactions of the followers, for general finite state Markov chains, under the average-cost-per-stage criteria. Next, this algorithm is analyzed in the context of weakly-coupled Markov chains to compute near-optimal strategies from a reduced-order aggregate model. The robustness of the near-optimal solution is established, and the multimodel feature of the computational algorithm is highlighted.     

A note on a canonical theory with undecidable unification and matching problem

A natural example of a canonical theory with undecidable unification and matching problem is presented.     

A statistical model for undecidable viral detection

This paper presents a statistical model of the malware detection problem. Where Chess and White (An undetectable computer virus. In: Virus Bulletin Conference, 2000) just partially addressed this issue and gave only existence results, we give here constructive results of undetectable malware. We show that any existing detection techniques can be modelled by one or more statistical tests. Consequently, the concepts of false positive and non detection are precisely defined. The concept of test simulability is then presented and enables us to gives constructive results how undetectable malware could be developped by an attacker. Practical applications of this statistical model are proposed. Finally, we give a statistical variant of Cohen’s undecidability results of virus detection.     

Characteristic of exit moments and models of enlargement of states for finite markov chains in terms of global memory functionals

A notion of local- and global-memory functionate for discrete-type distributions is introduced by analogy with the notion of the memory for continuous-type distributions introduced in Muth’s papers. In the class of PH-distributions (i.e., of distributions of the time of Markov chain exit from a subset of states) the necessary and sufficient conditions are obtained for the case where the exit time has an exponential (continuous-time) or a geometric (discrete time) distribution. A new notion of a global memory functional for decomposition of the state space of a finite Markov chain is introduced. Its properties as a measure of quality of decomposition and enlargement of a state space are studied. The asymptotic optimality is proved. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 110–120, May–June, 2000.     

Using the Manhattan distance for computing the multiobjective Markov chains problem

This paper presents a novel method for computing the multi-objective problem in the case of a metric state space using the Manhattan distance. The problem is restricted to a class of ergodic controllable finite Markov chains. This optimization approach is developed for converging to an optimal solution that corresponds to a strong Pareto optimal point in the Pareto front. The method consists of a two-step iterated procedure: (a) the first step consists on an approximation to a strong Pareto optimal point and, (b) the second step is a refinement of the previous approximation. We formulate the problem adding the Tikhonov's regularization method to ensure the convergence of the cost-functions to a unique strong point into the Pareto front. We prove that there exists an optimal solution that is a strong Pareto optimal solution and it is the closest solution to the utopian point of the Pareto front. The proposed solution is validated theoretically and by a numerical example considering the vehicle routing planning problem.     

Predicting torsion angles in amino acid protein sequences based on a bayesian classification procedure on markov chains

Torsion angles formed by C ^α atoms of four neighboring residues are predicted using a Bayesian classification procedure on nonstationary Markov chains. The predicted sequence of torsion angles is used to construct a three-dimensional protein structure on Z ³ lattice.