Ranking Templates for Linear Loops Leike, Jan; Heizmann, Matthias
Logical methods in computer science,
03/2015, Volume:
11, Issue 1
Journal Article
Peer reviewed
Open access
We present a new method for the constraint-based synthesis of termination
arguments for linear loop programs based on linear ranking templates. Linear
ranking templates are parameterized, ...well-founded relations such that an
assignment to the parameters gives rise to a ranking function. Our approach
generalizes existing methods and enables us to use templates for many different
ranking functions with affine-linear components. We discuss templates for
multiphase, nested, piecewise, parallel, and lexicographic ranking functions.
These ranking templates can be combined to form more powerful templates.
Because these ranking templates require both strict and non-strict
inequalities, we use Motzkin's transposition theorem instead of Farkas' lemma
to transform the generated $\exists\forall$-constraint into an
$\exists$-constraint.
Termination of programs is probably the most famous undecidable problem in computer science. Despite this undecidability result, a lot of effort has been spent on improving algorithms that prove ...termination of loops, which is one of the fundamental aspects of software reliability analysis. These algorithms usually focus on finding an appropriate ranking function for the loop, which proves its termination. In this paper, we focus on handling the synthesis problem of nested ranking functions and multi-phase ranking functions for loop programs. We first reduce the problem of a nested ranking function synthesis to the existence problem of a hyperplane separating classes of data. This allows us to leverage Support-Vector Machines (SVM) techniques for the synthesis of nested ranking functions. SVM are supervised learning algorithms that are used to classify data; they work by finding a hyperplane separating data points parted into two classes. We show how to carefully define the data points so that the separating hyperplane gives rise to a nested ranking function for the loop. Then we use this algorithm for nested ranking functions synthesis as a subprocedure to devise a sound algorithm which incrementally synthesizes multi-phase ranking functions. Experimental results confirm the effectiveness of our SVM-based synthesis of nested and multi-phase ranking functions.
Abstract
Transportation theory is the name given to the study of optimal transportation (OT) and resource allocation in mathematics and economics. In any discipline of science and technology, ...engineering, medicine, and management, uncertainty plays a critical role. Fuzzy Mathematics (FM) and fuzzy logic (FL) are used in Artificial Intelligence (AI) to process natural language and are frequently employed in decision making (DM). In this paper, using three ranking function to treat the fuzzy transportation model, two of them are Yager and Maleki ranking functions and the other is proposal and suggest depend up on of Yager ranking function based on trapezoidal fuzzy membership function when the total demand, cost of transportation, and the total amount of product (supply) are fuzzy, then the fuzzy model shrinkage to traditional or crisp model. Finally solving these models to the real data that we got it from The General Company for Food Products Abo ghreeb / Iraq.
The main aim of the presented study is estimating the parameters of Weibull distribution by utilizing simulation to generated the samples size when n=10, 50,100. Considering in the current study the ...parameters estimator of Weibull membership function, then using the nonlinear membership function for Gaussian function to find the fuzzy number for these parameters estimator. After that utilizing the ranking function to transform the fuzzy number to crisp number.
Ranked batch-mode active learning Cardoso, Thiago N.C.; Silva, Rodrigo M.; Canuto, Sérgio ...
Information sciences,
02/2017, Volume:
379
Journal Article
Peer reviewed
•We introduce a new way of thinking about Batch-Mode Active Learning.•A method for ranking unlabeled sets based on informativeness is proposed.•Our results are superior (up to 25%) to pool-based ...batch-mode active learning.•Our method is a drop-in replacement for batch-mode methods without their limitations.•It is also superior to density-sensitive active learning methods.
We introduce a new paradigm for Ranked Batch-Mode Active Learning. It relaxes traditional Batch-Mode Active Learning (BMAL) methods by generating a query whose answer is an optimized ranked list of instances to be labeled, according to some quality criteria, allowing batches to be of arbitrarily large sizes. This new paradigm avoids the main problem of traditional BMAL, namely the frequent stops for manual labeling, reconciliation and model reconstruction. In this article, we formally define this problem and introduce a framework that iteratively and effectively builds the ranked list. Our experimental evaluation shows our proposed Ranked Batch approach significantly reduces the number of algorithm executions (and, consequently, the manual labeling delays) while maintaining or even improving the quality of the selected instances. In fact, when using only unlabeled data, our results are much better than those produced by pool-based batch-mode active learning methods that rely on already labeled seeds or update their models with labeled instances, with gains of up to 25% in MacroF1. Finally, our solutions are also more effective than density-sensitive active learning methods in most of the envisioned scenarios, as demonstrated by our experiments.
Display omitted
► Ranking function. ► Generalized trapezoidal fuzzy number. ► Fuzzy transportation problems.
In the literature, several algorithms are proposed for solving the transportation problems ...in fuzzy environment but in all the proposed algorithms the parameters are represented by normal fuzzy numbers. Chen Operations on fuzzy numbers with function principal, Tamkang Journal of Management Science 6 (1985) 13–25 pointed out that in many cases it is not to possible to restrict the membership function to the normal form and proposed the concept of generalized fuzzy numbers. There are several papers in the literature in which generalized fuzzy numbers are used for solving real life problems but to the best of our knowledge, till now no one has used generalized fuzzy numbers for solving the transportation problems. In this paper, a new algorithm is proposed for solving a special type of fuzzy transportation problems by assuming that a decision maker is uncertain about the precise values of transportation cost only but there is no uncertainty about the supply and demand of the product. In the proposed algorithm transportation costs are represented by generalized trapezoidal fuzzy numbers. To illustrate the proposed algorithm a numerical example is solved and the obtained results are compared with the results of existing approaches. Since the proposed approach is a direct extension of classical approach so the proposed approach is very easy to understand and to apply on real life transportation problems for the decision makers.
In fuzzy decision-making, incomplete information always leads to uncertain and partially reliable judgements. The emergence of fuzzy set theory helps decision-makers in handling uncertainty and ...vagueness when making judgements. Intuitionistic Fuzzy Numbers (IFN) measure the degree of uncertainty better than classical fuzzy numbers, while Z-numbers help to highlight the reliability of the judgements. Combining these two fuzzy numbers produces Intuitionistic Z-Numbers (IZN). Both restriction and reliability components are characterized by the membership and non-membership functions, exhibiting a degree of uncertainties that arise due to the lack of information when decision-makers are making preferences. Decision information in the form of IZN needs to be defuzzified during the decision-making process before the final preferences can be determined. This paper proposes an Intuitive Multiple Centroid (IMC) defuzzification of IZN. A novel Multi-Criteria Decision-Making (MCDM) model based on IZN is developed. The proposed MCDM model is implemented in a supplier selection problem for an automobile manufacturing company. An arithmetic averaging operator is used to aggregate the preferences of all decision-makers, and a ranking function based on centroid is used to rank the alternatives. The IZN play the role of representing the uncertainty of decision-makers, which finally determine the ranking of alternatives.
There are multiple ways of defining nonmonotonic inference relations based on a conditional knowledge base. While the axiomatic system P is an important standard for such plausible nonmonotonic ...reasoning, inference relations obtained from system Z or from c-representations have been designed which go beyond system P by selecting preferred models for inference. For any class of models M, we propose the notion of weakly skeptical inference, first introduced in an ECAI conference paper this article revises and extends, that lies between skeptical and credulous inference with respect to M. Weakly skeptical c-inference properly extends skeptical c-inference, but avoids disadvantages of a too liberal credulous c-inference. We extend the concepts of skeptical, weakly skeptical, and credulous c-inference modes by taking models obtained from different minimality criteria into account. We illustrate the usefulness of the obtained inference relations and show that they fulfill various desirable properties put forward for nonmonotonic reasoning. Furthermore, we elaborate in detail the interrelationships among the inference relations when taking the different inference modes and various classes of minimal models into account.
PDF
