On the recognition of the tautological nature of propositional formulas

A formal language whose propositions express (in some sense) the properties of propositional formulas is described in the paper. For a certain subset of propositions of this language it is proved that each of them defines a class of propositional formulas, on which it is possible to recognize the tautological nature in a time polynomially dependent on the formula's length.Translated fromZapiski Nauchnykh Seminarov Leningradskogo Matematicheskogo, Otdeleniyaim. V. A.Steklova Akad.Nauk SSSR, Vol. 60, pp. 197–206,1976. Result announced December 4, 1974.     

The polynomial bounds of proof complexity in Frege systems

The concept of a determinative set of variables for a propositional formula was introduced by one of the authors, which made it possible to distinguish the set of hard-determinable formulas. The proof complexity of a formula of this sort has exponential lower bounds in some proof systems of classical propositional calculus (cut-free sequent system, resolution system, analytic tableaux, cutting planes, and bounded Frege systems). In this paper we prove that the property of hard-determinability is insufficient for obtaining a superpolynomial lower bound of proof lines (sizes) in Frege systems: an example of a sequence of hard-determinable formulas is given whose proof complexities are polynomially bounded in every Frege system.     

A Bounded Translation of Intuitionistic Propositional Logic into Basic Propositional Logic

In this paper we prove a bounded translation of intuitionistic propositional logic into basic propositional logic. Our new theorem, compared with the translation theorem in [1], has the advantage that it gives an effective bound on the translation, depending on the complexity of formulas.     

Generalized periodicity and primitivity for words

Starting from six kinds of periodicity of words we define six sets of words which are primitive in different senses and we investigate their relationships. We show that only three of the sets are external Marcus contextual languages with choice but none of them is an external contextual language without choice or an internal contextual language. For the time complexity of deciding any of our sets by one-tape Turing machines, n ² is a lower bound and this is optimal in two cases. The notions of roots and degrees of words and languages, which are strongly connected to periodicity and primitivity, are also considered, and we show that there can be an arbitrarily large gap between the complexity of a language and that of its roots. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Computing generalized Nash equilibria by polynomial programming

We present a new way to solve generalized Nash equilibrium problems. We assume the feasible set to be compact. Furthermore all functions are assumed to be polynomials. However we do not impose convexity on either the utility functions or the action sets. The key idea is to use Putinar’s Positivstellensatz, a representation result for positive polynomials, to replace each agent’s problem by a convex optimization problem. The Nash equilibria are then feasible solutions to a system of polynomial equations and inequalities. Our application is a model of the New Zealand electricity spot market with transmission losses based on a real dataset.     

Propositional distances and compact preference representation

Distances between possible worlds play an important role in logic-based knowledge representation (especially in belief change, reasoning about action, belief merging and similarity-based reasoning). We show here how they can be used for representing in a compact and intuitive way the preference profile of an agent, following the principle that given a goal G, then the closer a world w to a model of G, the better w. We give an integrated logical framework for preference representation which handles weighted goals and distances to goals in a uniform way. Then we argue that the widely used Hamming distance (which merely counts the number of propositional symbols assigned a different value by two worlds) is generally too rudimentary and too syntax-sensitive to be suitable in real applications; therefore, we propose a new family of distances, based on Choquet integrals, in which the Hamming distance has a position very similar to that of the arithmetic mean in the class of Choquet integrals.     

条件概率真度的相似度及伪距离

基于条件概率的思想,在连续值命题逻辑系统中引入赋值密度函数概念,给出了公式的概率真度、条件概率真度的定义,定义了公式间的相似度和伪距离并证明了概率真度的推理规则.     

The Pearson system of utility functions

This paper describes a parametric family of utility functions for decision analysis. The parameterization embeds the HARA class in a four-parameter representation for the risk aversion function. The resulting utility functions can have only four shapes: concave, convex, S-shaped, and reverse S-shaped. This makes the family suited for both expected utility and prospect theory. The paper also describes an alternative technique to estimate the four parameters from elicited utilities, which is simpler than standard fitting by minimization of the mean quadratic error.     

Computation Models for Parameterized Complexity

A parameterized computational problem is a set of pairs (x, k), where k is a distinguished item called “parameter”. FPT is the class of fixed-parameter tractable problems: for any fixed value of k, they are solvable in time bounded by a polynomial of degree α, where α is a constant not dependent on the parameter. In order to deal with parameterized intractability, Downey and Fellows have introduced a hierarchy of classes W[l] ? W[2] ? ? containing likely intractable parameterized problems, and they have shown that such classes have many natural, complete languages. In this paper we analyze several variations of the halting problem for nondeterministic Turing machines with parameterized time, and we show that its parameterized complexity strongly depends on some resources like the number of tapes, head and internal states, and on the size of the alphabet. Notice that classical polynomial-time complexity fails in distinguishing such features. As byproducts, we show that parameterized complexity is a useful tool for the study of the intrinsic power of some computational models, and we underline the different “computational powers” of some levels of the parameterized hierarchy.     

Monte Carlo simulation techniques for group decision making with incomplete information

In this paper we deal with group decision-making problems where several decision makers elicit their own preferences separately. The decision makers’ preferences are quantified using a decision support system, which admits incomplete information concerning the decision makers’ responses to the questions they are asked. Consequently, each decision maker proposes classes of utility functions and attribute weight intervals for the different attributes. We introduce an approach based on Monte Carlo simulation techniques for aggregating decision maker preferences that could be the starting point for a negotiation process, if necessary. The negotiation process would basically involve the decision maker tightening the imprecise component utilities and weights to output more meaningful results and achieve a consensus alternative. We focus on how attribute weights and the component utilities associated with a consequence are randomly generated in the aggregation process taking into account the decision-makers’ preferences, i.e., their respective attribute weight intervals and classes of utility functions. Finally, an application to the evaluation of intervention strategies for restoring a radionuclide contaminated lake illustrates the usefulness and flexibility of this iterative process.     

命题逻辑公式的压缩表示及其相应的形式系统

提出一种将命题逻辑公式压缩表示的方法--公式的压缩图,给出相应的形式系统,并证明该系统的证明效率比传统相继式演算系统Gentzen\{cut}有指数级的提高,从而为命题逻辑提供了一种新的有效的推理系统.     

Additive DEA based on MCDA with imprecise information

This work exploits links between Data Envelopment Analysis (DEA) and multicriteria decision analysis (MCDA), with decision making units (DMUs) playing the role of decision alternatives. A novel perspective is suggested on the use of the additive DEA model in order to overcome some of its shortcomings, using concepts from multiattribute utility models with imprecise information. The underlying idea is to convert input and output factors into utility functions that are aggregated using a weighted sum (additive model of multiattribute utility theory), and then let each DMU choose the weights associated with these functions that minimize the difference of utility to the best DMU. The resulting additive DEA model with oriented projections has a clear rationale for its efficiency measures, and allows meaningful introduction of constraints on factor weights.     

Logical and algorithmic properties of stable conditional independence

The logical and algorithmic properties of stable conditional independence (CI) as an alternative structural representation of conditional independence information are investigated. We utilize recent results concerning a complete axiomatization of stable conditional independence relative to discrete probability measures to derive perfect model properties of stable conditional independence structures. We show that stable CI can be interpreted as a generalization of Markov networks and establish a connection between sets of stable CI statements and propositional formulas in conjunctive normal form. Consequently, we derive that the implication problem for stable CI is coNP-complete. Finally, we show that Boolean satisfiability (SAT) solvers can be employed to efficiently decide the implication problem and to compute concise, non-redundant representations of stable CI, even for instances involving hundreds of random variables.     

A simple logic for reasoning about incomplete knowledge

The semantics of modal logics for reasoning about belief or knowledge is often described in terms of accessibility relations, which is too expressive to account for mere epistemic states of an agent. This paper proposes a simple logic whose atoms express epistemic attitudes about formulae expressed in another basic propositional language, and that allows for conjunctions, disjunctions and negations of belief or knowledge statements. It allows an agent to reason about what is known about the beliefs held by another agent. This simple epistemic logic borrows its syntax and axioms from the modal logic KD. It uses only a fragment of the S5 language, which makes it a two-tiered propositional logic rather than as an extension thereof. Its semantics is given in terms of epistemic states understood as subsets of mutually exclusive propositional interpretations. Our approach offers a logical grounding to uncertainty theories like possibility theory and belief functions. In fact, we define the most basic logic for possibility theory as shown by a completeness proof that does not rely on accessibility relations.     

ON THE REASONING EXPRESSIONS AND THE NATURE OF DEDUCTION RULES

Reasoning expressions are those which express the reaasoning procedure by means ofonly deduction rules and the initial formulas(axioms or assumptions)without the helpof any intermediate results.They express the procedure systematically,completely andconcisely.The deduction rules are mappings from formulas(premises)to formula(conclusion).The elementary rules are certain propositional connectives(but notnecessarily truth functions)while the higher rules are certain quantifiers.Besides,thedetachment rule is an inverse of the connective implication,and is itself the kernel ofdeduction method;while another inverse of implication(i.e.the suggestion rule)is thekernel of induction method.     

基于语言值的变权综合决策方法

给出一种新的语言值乘法和加法运算,同时利用扩展原理、格贴近度和择近原则等理论论证所给运算法则的科学性,在此基础上建立一个基于二元组的纯语言值加权综合决策模型,随后,在语言值与实数集[0,1]之间定义两个转换函数,由此引入语言值效用向量等概念,借助语言值效用向量和实数型状态变权向量导出语言值状态变权向量,进而建立相应的语言值变权公式和变权综合决策模型。     

A singular integral equation with the Cauchy kernel on a closed interval in a class of distributions

In the present paper, we introduce the notion of a singular integral with the Cauchy kernel for distributions and consider a singular integral equation with the Cauchy kernel on a closed interval for the case in which the right-hand side is a distribution that admits a representation in the form of the sum of a distribution vanishing in neighborhoods of the endpoints and an ordinary function satisfying the Hölder condition. The solution is also sought in the form of a distribution. Distributions are treated as linear functionals on some test functions. We analyze the solvability of the equation in the class of distributions and obtain explicit formulas for the inversion of this equation, similar to formulas for ordinary solutions. To analyze the solvability of the singular integral equation, we use an approach based on the consideration of the Riemann boundary value problem for analytic functions with a generalized boundary condition. When stating and studying this problem, we use the results in [1, 2].Translated from Differentsialnye Uravneniya, Vol. 40, No. 9, 2004, pp. 1208–1218.Original Russian Text Copyright © 2004 by Setukha.