Chance-constrained programming with fuzzy stochastic coefficients

We consider fuzzy stochastic programming problems with a crisp objective function and linear constraints whose coefficients are fuzzy random variables, in particular of type L-R. To solve this type of problems, we formulate deterministic counterparts of chance-constrained programming with fuzzy stochastic coefficients, by combining constraints on probability of satisfying constraints, as well as their possibility and necessity. We discuss the possible indices for comparing fuzzy quantities by putting together interval orders and statistical preference. We study the convexity of the set of feasible solutions under various assumptions. We also consider the case where fuzzy intervals are viewed as consonant random intervals. The particular cases of type L-R fuzzy Gaussian and discrete random variables are detailed.     

CTL AgentSpeak(L): A specification language for agent programs

This work introduces CTL AgentSpeak(L), a logic to specify and verify expected properties of rational agents implemented in the well-known agent oriented programming language AgentSpeak(L). Our approach is closely related to the BDICTL multi-modal logic, used to reason about agents in terms of their beliefs (B), desires (D), intentions (I), and the temporal logic CTL. A new interpretation for the temporal operators, grounded in the transition system induced by the operational semantics of AgentSpeak(L), is proposed. The main contribution of the approach is a better understanding of the relation between the programming language and its logical specification, enabling us to prove expected or desired properties for any agent programmed in the language, e.g., commitment strategies. The results, as well as the specification language proposed, are very useful to reconcile computational and philosophical aspects of practical reasoning, e.g., approaching single-minded commitment as a policy-based reconsideration case.     

Lewis meets Brouwer: Constructive strict implication

C.I. Lewis invented modern modal logic as a theory of “strict implication” $?$. Over the classical propositional calculus one can as well work with the unary box connective. Intuitionistically, however, the strict implication has greater expressive power than $\square$ and allows to make distinctions invisible in the ordinary syntax. In particular, the logic determined by the most popular semantics of intuitionistic $\mathsf{K}$ becomes a proper extension of the minimal normal logic of the binary connective. Even an extension of this minimal logic with the “strength” axiom, classically near-trivial, preserves the distinction between the binary and the unary setting. In fact, this distinction has been discovered by the functional programming community in their study of “arrows” as contrasted with “idioms”. Our particular focus is on arithmetical interpretations of intuitionistic $?$ in terms of preservativity in extensions of $\mathsf{HA}$, i.e., Heyting’s Arithmetic.     

A system of elliptic equations arising in Chern-Simons field theory

We prove the existence of topological vortices in a relativistic self-dual Abelian Chern-Simons theory with two Higgs particles and two gauge fields through a study of a coupled system of two nonlinear elliptic equations over R². We present two approaches to prove existence of solutions on bounded domains: via minimization of an indefinite functional and via a fixed point argument. We then show that we may pass to the full R² limit from the bounded-domain solutions to obtain a topological solution in R².     

Multiple optima in local search

We consider the application of local search methods to the maximum independent set problem. These methods employ a relation R on the power set of the graph's vertices that identifies a set of vertices, U, with a collection of subsets of vertices, R(U), called the neighbors of U. If each set U has only polynomially many neighbors then we say that R is polynomially bounded. Further, given a graph, G, we call a permutation of G, φ(G), to be any graph that arises from G by relabeling the vertices. Our main result is slightly stronger than the following: we construct a graph G such that, for all polynomially bounded relations, R, most permutations φ(G) of the graph contain exponentially many strict local optima that are not global optima. That is, a single graph (up to relabelling of the vertices) exists that soundly defeats all polynomially bounded relations R. Corollaries follow for 0–1 integer programming and other hard optimization problems.     

Inquisitive logic as an epistemic logic of knowing how

In this paper, we present an alternative interpretation of propositional inquisitive logic as an epistemic logic of knowing how. In our setting, an inquisitive logic formula α being supported by a state is formalized as knowing how to resolve α (more colloquially, knowing how α is true) holds on the S5 epistemic model corresponding to the state. Based on this epistemic interpretation, we use a dynamic epistemic logic with both know-how and know-that operators to capture the epistemic information behind the innocent-looking connectives in inquisitive logic. We show that the set of valid know-how formulas corresponds precisely to the inquisitive logic. The main result is a complete axiomatization with intuitive axioms using the full dynamic epistemic language. Moreover, we show that the know-how operator and the dynamic operator can both be eliminated without changing the expressivity over models, which is consistent with the modal translation of inquisitive logic existing in the literature. We hope our framework can give an intuitive alternative interpretation to various concepts and technical results in inquisitive logic, and also provide a powerful and flexible tool to handle both the inquisitive reasoning and declarative reasoning in an epistemic context.     

A new approach to multivariate adaptive regression splines by using Tikhonov regularization and continuous optimization

This paper introduces a model-based approach to the important data mining tool Multivariate adaptive regression splines (MARS), which has originally been organized in a more model-free way. Indeed, MARS denotes a modern methodology from statistical learning which is important in both classification and regression, with an increasing number of applications in many areas of science, economy and technology. It is very useful for high-dimensional problems and shows a great promise for fitting nonlinear multivariate functions. The MARS algorithm for estimating the model function consists of two algorithms, these are the forward and the backward stepwise algorithm. In our paper, we propose not to use the backward stepwise algorithm. Instead, we construct a penalized residual sum of squares for MARS as a Tikhonov regularization problem which is also known as ridge regression. We treat this problem using continuous optimization techniques which we consider to become an important complementary technology and model-based alternative to the concept of the backward stepwise algorithm. In particular, we apply the elegant framework of conic quadratic programming. This is an area of convex optimization which is very well-structured, herewith, resembling linear programming and, hence, permitting the use of powerful interior point methods. Based on these theoretical and algorithmical studies, this paper also contains an application to diabetes data. We evaluate and compare the performance of the established MARS and our new CMARS in classifying diabetic persons, where CMARS turns out to be very competitive and promising.     

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.     

The implementation of Fprolog—A fuzzy Prolog interpreter

Prolog, a programming language based on the first order predicate calculus, has been widely used in artificial intelligence research. One of its shortcomings is the lack of a natural mechanism to deal with uncertainty.A possible solution to this problem, outlined here, is to base Prolog on fuzzy logic rather than on conventional two-valued logic. This leads to a more general system, of which standard Prolog is a special case. To give the system greater flexibility, the fuzzy Prolog interpreter can link with the Fril system developed at Bristol, yielding a powerful language with breadth-first and depth-first search capabilities.     

Full field algebras, operads and tensor categories

We study the operadic and categorical formulations of (conformal) full field algebras. In particular, we show that a grading-restricted R×R-graded full field algebra is equivalent to an algebra over a partial operad constructed from spheres with punctures and local coordinates. This result is generalized to conformal full field algebras over VL⊗VR, where VL and VR are two vertex operator algebras satisfying certain finiteness and reductivity conditions. We also study the geometry interpretation of conformal full field algebras over VL⊗VR equipped with a nondegenerate invariant bilinear form. By assuming slightly stronger conditions on VL and VR, we show that a conformal full field algebra over VL⊗VR equipped with a nondegenerate invariant bilinear form exactly corresponds to a commutative Frobenius algebra with a trivial twist in the category of VL⊗VR-modules. The so-called diagonal constructions [Y.-Z. Huang, L. Kong, Full field algebras, arXiv: math.QA/0511328] of conformal full field algebras are given in tensor-categorical language.     

Theory of Semi-Instantiation in Abstract Argumentation

We study instantiated abstract argumentation frames of the form (S, R, I), where (S, R) is an abstract argumentation frame and where the arguments x of S are instantiated by I(x) as well formed formulas of a well known logic, for example as Boolean formulas or as predicate logic formulas or as modal logic formulas. We use the method of conceptual analysis to derive the properties of our proposed system. We seek to define the notion of complete extensions for such systems and provide algorithms for finding such extensions. We further develop a theory of instantiation in the abstract, using the framework of Boolean attack formations and of conjunctive and disjunctive attacks. We discuss applications and compare critically with the existing related literature.     

On vectorizations of unary generalized quantifiers

Vectorization of a class of structures is a natural notion in finite model theory. Roughly speaking, vectorizations allow tuples to be treated similarly to elements of structures. The importance of vectorizations is highlighted by the fact that if the complexity class PTIME corresponds to a logic with reasonable syntax, then it corresponds to a logic generated via vectorizations by a single generalized quantifier (Dawar in J Log Comput 5(2):213–226, 1995). It is somewhat surprising, then, that there have been few systematic studies of the expressive power of vectorizations of various quantifiers. In the present paper, we consider the simplest case: the cardinality quantifiers C _S . We show that, in general, the expressive power of the vectorized quantifier logic ${{\rm FO}(\{{\mathsf C}_S^{(n)}\, | \, n \in \mathbb{Z}_+\})}$ is much greater than the expressive power of the non-vectorized logic FO(C _S ).     

Polynomials That Force a Unital Ring to be Commutative

We characterize polynomials f with integer coefficients such that a ring with unity R is necessarily commutative if f(R) = 0, in the sense that f(x) = 0 for all ${x \in R}$ . Such a polynomial must be primitive, and for primitive polynomials the condition f(R) = 0 forces R to have nonzero characteristic. The task is then reduced to considering rings of prime power characteristic and the main step towards the full characterization is a characterization of polynomials f such that R is necessarily commutative if f(R) = 0 and R is a unital ring of characteristic some power of a fixed prime p.     

First-order theories for pure Prolog programs with negation

The standard theory of logic programming is not applicable to Prolog programs even not to pure code. Modifying the theory to take account of reality more is the motivation of this article. For this purpose we introduce the -completion and the inductive extension of a logic program. Both are first-order theories in a language with operators for success, failure and termination of goals. The -completion of a logic program is a sound and complete axiomatization of the Prolog depth-first search under certain natural conditions; the inductive extension of the -completion is a suitable theory for proving termination and equivalence of pure Prolog programs with negation.Sponsored by the Alexander von Humboldt Foundation, Germany     

Oil Exploration: A Property of Beale's Model

In this paper we assume that an oil company has k areas in which to drill and occurrences of undiscovered oilfields are represented by the model of Beale. The company is seeking a strategy for drilling that maximizes its expected return under the constraint that the total amount spent on drilling in all areas must not exceed R. This leads to an integer programming problem. We establish that the expected return functions for the separate areas are concave and that this property can be used to reduce the computational effort required to find an optimal solution.     

Rings and semigroups with permutable zero products

We consider rings R, not necessarily with 1, for which there is a nontrivial permutation σ on n letters such that x₁?x_n=0 implies x_σ(1)?x_σ(n)=0 for all x₁,…,x_n∈R. We prove that this condition alone implies very strong permutability conditions for zero products with sufficiently many factors. To this end we study the infinite sequences of permutation groups P_n(R) consisting of those permutations σ on n letters for which the condition above is satisfied in R. We give the full characterization of such sequences both for rings and for semigroups with 0. This enables us to generalize some recent results by Cohn on reversible rings and by Lambek, Anderson and Camillo on rings and semigroups whose zero products commute. In particular, we prove that rings with permutable zero products satisfy the Köthe conjecture.     

Higher order duality in multiobjective fractional programming with support functions

In this paper a new class of higher order (F,ρ,σ)-type I functions for a multiobjective programming problem is introduced, which subsumes several known studied classes. Higher order Mond-Weir and Schaible type dual programs are formulated for a nondifferentiable multiobjective fractional programming problem where the objective functions and the constraints contain support functions of compact convex sets in Rn. Weak and strong duality results are studied in both the cases assuming the involved functions to be higher order (F,ρ,σ)-type I. A number of previously studied problems appear as special cases.     

Bilinear spaces over a fixed field are simple unstable

We study the model theory of vector spaces with a bilinear form over a fixed field. For finite fields this can be, and has been, done in the classical framework of full first-order logic. For infinite fields we need different logical frameworks. First we take a category-theoretic approach, which requires very little set-up. We show that linear independence forms a simple unstable independence relation. With some more work we then show that we can also work in the framework of positive logic, which is much more powerful than the category-theoretic approach and much closer to the classical framework of full first-order logic. We fully characterise the existentially closed models of the arising positive theory. Using the independence relation from before we conclude that the theory is simple unstable, in the sense that dividing has local character but there are many distinct types. We also provide positive version of what is commonly known as the Ryll-Nardzewski theorem for ω-categorical theories in full first-order logic, from which we conclude that bilinear spaces over a countable field are ω-categorical.     

Identifying large robust network clusters via new compact formulations of maximum k-club problems

Network robustness issues are crucial in a variety of application areas. In many situations, one of the key robustness requirements is the connectivity between each pair of nodes through a path that is short enough, which makes a network cluster more robust with respect to potential network component disruptions. A k-club, which by definition is a subgraph of a diameter of at most k, is a structure that addresses this requirement (assuming that k is small enough with respect to the size of the original network). We develop a new compact linear 0-1 programming formulation for finding maximum k-clubs that has substantially fewer entities compared to the previously known formulation (O(kn²) instead of O(n^k+1), which is important in the general case of k > 2) and is rather tight despite its compactness. Moreover, we introduce a new related concept referred to as an R-robust k-club (or, (k, R)-club), which naturally arises from the developed k-club formulations and extends the standard definition of a k-club by explicitly requiring that there must be at least R distinct paths of length at most k between all pairs of nodes. A compact formulation for the maximum R-robust k-club problem is also developed, and error and attack tolerance properties of the important special case of R-robust 2-clubs are investigated. Computational results are presented for multiple types of random graph instances.     

Symmetries of PDE systems and correspondences between jet spaces

Let M be a manifold. A PDE system can be prolonged to another one R^?⊆T^?M (Jiménez et al. (2005) [10]). In analogy with the higher-order symmetries, symmetries of R^? will be called higher-dimensional symmetries of R. For a broad class of PDE systems we prove that every (infinitesimal or finite) symmetry of R comes from another one of R^?. We show that R^? does not have internal (infinitesimal) symmetries (modulo trivial symmetries). This fact allows us, in the infinitesimal case, to compute the internal symmetries of R as external symmetries of R^?. We also give an algorithmic method to obtain solutions of R invariant by a given internal symmetry.