Log diameter restricted bottom-up triangle cellular acceptors

The languages accepted by bottom-up triangle cellular acceptors (UTCAs) in log diameter time are the same as those accepted by UTCAs in which a cell's new state depends only on its sons' states and not on its own preceding state. This set of languages remains the same if we allow log diameter + constant time, but it increases if we allow 2 log diameter time. It is also shown that this set is the same as the set of languages generated by a special class of “power of 2” OL-systems.     

Some decision problems related to the reachability problem for Petri nets

In this paper, we show that (1) the question to decide whether a given Petri net is consistent, M_o-reversible or live is reduced to the reachability problem in a unified manner, (2) the reachability problem for Petri nets is equivalent to the equality problem and the inclusion problem for the sets of all firing sequences of two Petri nets, (3) the equality problem for the sets of firing sequences of two Petri nets with only two unbounded places under homomorphism is undecidable, (4) the coverability and reachability problems are undecidable for generalized Petri nets in which a distinguished transition has priority over the other transitions, and (5) the reachability problem is undecidable for generalized Petri nets in which some transitions can reset a certain place to zero marking.     

Generalised bottom-up pruning: A model level combination of decision trees

A generalisation of bottom-up pruning is proposed as a model level combination method for a decision tree ensemble. Bottom up pruning on a single tree involves choosing between a subtree rooted at a node, and a leaf, dependant on a pruning criterion. A natural extension to an ensemble of trees is to allow subtrees from other ensemble trees to be grafted onto a node in addition to the operations of pruning to a leaf and leaving the existing subtree intact. Suitable pruning criteria are proposed and tested for this multi-tree pruning context. Gains in both performance and in particular compactness over individually pruned trees are observed in tests performed on a number of datasets from the UCI database. The method is further illustrated on a churn prediction problem in the telecommunications domain.     

A method for multiple pseudo-criteria decision problems

Most complex decision problems involve conflicting multicriteria to be reconciled. It is not uncommon that the numerical values of alternatives of some criteria are subject to imprecision, uncertainty, and indetermination. The concept of pseudo-criterion and its two thresholds allow them to be taken into account. So far, outranking relation methods, which are called ELECTRE I–IV and others, in which an outranking relation between alternatives is constructed from pseudo-criteria have been developed. Among others, ELECTRE III is the most familiar and has been widely used. The purpose of this paper is to propose a new procedure for treating the pseudo-criterion based on the ternary AHP. This procedure differs from ELECTRE III and requires only the incomplete information on the weights but not precise weights. Strict preference, weak preference, and indifference relations associated with a pseudo-criterion are formulated by a ternary comparison. In general, the procedures for dealing with the pseudo-criterion necessarily involve a certain amount of arbitrariness. Therefore, it is preferable to derive the rankings of alternatives from several procedures for the pseudo-criterion in order to promote complementary viewpoints. Comparing our procedure with ELECTRE III, the strengths and weaknesses of the proposed procedure are discussed.Scope and purposeMost decision problems involve multiple and conflicting objectives, goals, or attributes. In the past three decades, many approaches have been developed. These include decision analysis based on multiattribute utility theory and interactive approaches based on the progressive articulation of preferences. They are built on sound theoretical foundations but rely on strict assumptions about the underlying preference structure. It is not uncommon that the numerical values of alternatives of some criteria are imprecise and ambiguous in complex decision problems. In such cases, the above approaches may not be appropriate. To cope with them, the concept of pseudo-criterion was introduced. So far, the outranking relation methods based on the pseudo-criterion which do not require the assumption of transitivity nor the complete comparability in the underlying preference structure have been developed. In this paper, we propose a new procedure for treating the pseudo-criterion based on the ternary AHP that differs from the outranking relation methods. In general, the procedures for dealing with the pseudo-criterion necessarily involve a certain amount of arbitrariness. Therefore, it is preferable to derive the rankings of alternatives from several procedures based on the pseudo-criterion in order to promote complementary viewpoints.     

Bad news on decision problems for patterns

We study the inclusion problem for pattern languages, which—due to Jiang et al. [T. Jiang, A. Salomaa, K. Salomaa, S. Yu, Decision problems for patterns, Journal of Computer and System Sciences 50 (1995) 53–63]—is known to be undecidable. More precisely, Jiang et al. demonstrate that there is no effective procedure deciding the inclusion for the class of all pattern languages over all alphabets. Most applications of pattern languages, however, consider classes over fixed alphabets, and therefore it is practically more relevant to ask for the existence of alphabet-specific decision procedures. Our first main result states that, for all but very particular cases, this version of the inclusion problem is also undecidable. The second main part of our paper disproves the prevalent conjecture on the inclusion of so-called similar E-pattern languages, and it explains the devastating consequences of this result for the intensive previous research on the most prominent open decision problem for pattern languages, namely the equivalence problem for general E-pattern languages.     

Three-level Stackelberg decision problems

Three-level Stackelberg decision problems are studied by using the inducible region concept. Through a systematic derivation, it is identified that the leader's control has dual purposes, which in general are not separable. A special class of problems is then considered, where explicit results are obtained.     

三角形对的快速相交测试

为提高碰撞检测的响应速度,提出了一种基于Ayellet算法的改进算法.该算法从代数的角度出发,首先快速排除掉三角形对不相交或共面的两种情况,然后分别计算一个三角形与另一个三角形所在平面的相交线段,最后检测这两条线段是否有公共点.如果有公共点则三角形对相交,反之则不相交.该算法也可以应用于类似的问题,如矩形对的相交测试,多边形对的相交测试.实验结果表明,该算法的速度优于改进前的算法.     

Some decision network designs for pattern classification

This article is concerned with the problem of labelling an unidentified parameter vector as belonging to one of a number of given classes. A cluster-analytic approach to the design of binary decision trees is discussed, but the major part of the paper is devoted to the construction of binary features and the creation of a binary feature vector as a means of pattern classification. Complete algorithms are described and some worked examples are also presented.     

SODPM: A sequence-oriented decision process model for unstructured group decision problems

Many approaches to the solutions of modern unstructured decision problems mainly involve modelling, information technology and group behaviour. The work of group decision-making can be viewed as a type of process plan that is reflected by its problem structure within which the thinking space is wide and innovative. This paper presents a Sequence-Oriented Decision Process Model (SODPM) that is based on the defined sequence of problem elements to help solve unstructured problems. A GDSSP (Group Decision Support System for Personnel Promotion) that embeds a predefined mechanism to perform decision process, decision model and decision choice is developed to experimentally demonstrate the SODPM. Empirical evaluation was conducted to derive the results for the research problems that include efficiency and group satisfaction. There were remarkable results: the SODPM can serve as a facilitative vehicle for opinion convergence and group satisfaction is highly positive. While the demonstrated domain for the example presented is personnel promotion, the proposed SODPM can be utilized to help solve the similar class of unstructured problems in other domains also.     

SODPM: a sequence-oriented decision process model for unstructured group decision problems

Many approaches to the solutions of modern unstructured decision problems mainly involve modelling, information technology and group behaviour. The work of group decision-making can be viewed as a type of process plan that is reflected by its problem structure within which the thinking space is wide and innovative. This paper presents a Sequence-Oriented Decision Process Model (SODPM) that is based on the defined sequence of problem elements to help solve unstructured problems. A GDSSP (Group Decision Support System for Personnel Promotion) that embeds a predefined mechanism to perform decision process, decision model and decision choice is developed to experimentally demonstrate the SODPM. Empirical evaluation was conducted to derive the results for the research problems that include efficiency and group satisfaction. There were remarkable results: the SODPM can serve as a facilitative vehicle for opinion convergence and group satisfaction is highly positive. While the demonstrated domain for the example presented is personnel promotion, the proposed SODPM can be utilized to help solve the similar class of unstructured problems in other domains also.     

Some new distance measures for type-2 fuzzy sets and distance measure based ranking for group decision making problems

In this paper, we propose some distance measures between type-2 fuzzy sets, and also a new family of utmost distance measures are presented. Several properties of different proposed distance measures have been introduced. Also, we have introduced a new ranking method for the ordering of type-2 fuzzy sets based on the proposed distance measure. The proposed ranking method satisfies the reasonable properties for the ordering of fuzzy quantities. Some properties such as robustness, order relation have been presented. Limitations of existing ranking methods have been studied. Further for practical use, a new method for selecting the best alternative, for group decision making problems is proposed. This method is illustrated with a numerical example.     

Some new distance measures for type-2 fuzzy sets and distance measure based ranking for group decision making problems

In this paper, we propose some distance measures between type-2 fuzzy sets, and also a new family of utmost distance measures are presented. Several properties of differ- ent proposed distance measures have been introduced. Also, we have introduced a new ranking method for the ordering of type-2 fuzzy sets based on the proposed distance measure. The proposed ranking method satisfies the reasonable prop- erties for the ordering of fuzzy quantities. Some properties such as robustness, order relation have been presented. Lim- itations of existing ranking methods have been studied. Fur- ther for practical use, a new method for selecting the best alternative, for group decision making problems is proposed. This method is illustrated with a numerical example.     

一种基于案例的多准则排序方法

针对带有间接偏好信息的多准则决策问题, 首先利用加性效用函数理论提出一种排序方法, 该方法通过构建一个简单的优化模型, 得到与间接偏好信息相容的各评价值的效用; 然后, 利用线性插值方法计算出剩下方案各评价值的效用, 进而得到所有方案的综合效用及排序; 最后, 通过实例验证了该方法的有效性和可行性.

     

The (n,k)-bounded emptiness-problem for probabilistic acceptors and related problems

Summary This paper investigates some problems which change their status from being unsolvable to solvable when varying the values of parameters. Let EMPTY(n, k) be the problem to decide for all rational probabilistic acceptors B with at most n states and k input symbols and for all rational numbers , whether the accepted language L(B,) is empty. It turns out that EMPTY(2, k) is solvable for all k, while EMPTY (9,9) and EMPTY (65,2) are not. Some problems of the theory of -rational power series are shown to be unsolvable, too, even for small values of the problemparameters.     

Decomposition of satisficing decision problems

This paper intends to clarify the decomposition of satisficing (decision) problems. Many researchers have studied the several aspects of satisficing problems verbal-logically (e.g. Cyert and March [2]; Simon [12]; Simon, Smithburgh, and Thompson [13]) or mathematically (e.g. Charnes and Cooper [1]; Ijiri [4]), and a formulation of satisficing problems under true uncertainty was done about one decade ago by M. D. Mesarovic and his group (e.g. Mesarovic, Macko, and Takahara [9]; Mesarovic and Takahara [10]). Its fundamental properties have been studied qualitatively by Matsuda and Takatsu [6–8]. However, the decomposition of satisficing problems has not been explicitly mentioned anywhere, even though implicit discussions have been given. Without the decomposition principles, we cannot solve large-scale satisficing problems, and cannot analyze or design coordination processes of hierarchical systems with satisficing problems as overall decision problems. Our study is mainly concentrated on the decomposition. Our results are somewhat restricted, because we deal with satisficing problems of relatively manageable forms. However, we can develop more sophisticated decompositions by combining our decomposition principles or by adding the other assumptions to our formulations. The results will be a starting point of a more complete study of satisficing decision problem solving.