Endolocality meets homomorphism-homogeneity: a new approach in the study of relational algebras

We study the problem of characterizing all relations that can be defined from the fundamental relations of a given relational structure using positive existential formulæ. The notion of κ-endolocality is introduced in order to measure the complexity of relational structures with respect to this task. The hierarchy of κ-endolocal structures is thoroughly analysed in algebraic and model-theoretic ways. Interesting cross-connections with homomorphism-homogeneous relational structures are revealed. The interrelations between endolocal relational structures and several model-theoretic notions are collected in the Main Theorem. This Main Theorem is demonstrated to be a useful tool for studying relational algebras and, in particular, weak Krasner algebras. For example, a short proof of F. Börners characterization of weak Krasner clones on a countable set is given.     

A general Weyl-type integration formula for isometric group actions

We show that integration over a G-manifold M can be reduced to integration over a minimal section Σ with respect to an induced weighted measure and integration over a homogeneous space G/N. We relate our formula to integration formulæ for polar actions and calculate some weight functions. In the case of a compact Lie group acting on itself via conjugation, we obtain a classical result of Hermann Weyl.     

Positional number systems with digits forming an arithmetic progression

A novel digit system that arises in a natural way in a graph-theoretical problem is studied. It is defined by a set of positive digits forming an arithmetic progression and, necessarily, a complete residue system modulo the base b. Since this is not enough to guarantee existence of a digital representation, the most significant digit is allowed to come from an extended set. We provide explicit formulæ for the j th digit in such a representation as well as for the length. Furthermore, we study digit frequencies and average lengths, thus generalising classical results for the base-b representation. For this purpose, an appropriately adapted form of the Mellin-Perron approach is employed.     

Negation and Paraconsistent Logics

Does there exist any equivalence between the notions of inconsistency and consequence in paraconsistent logics as is present in the classical two valued logic? This is the key issue of this paper. Starting with a language where negation (?{\neg}) is the only connective, two sets of axioms for consequence and inconsistency of paraconsistent logics are presented. During this study two points have come out. The first one is that the notion of inconsistency of paraconsistent logics turns out to be a formula-dependent notion and the second one is that the characterization (i.e. equivalence) appears to be pertinent to a class of paraconsistent logics which have double negation property.     

(Sub-)Differentiability of Probability Functions with Elliptical Distributions

In this paper we investigate probability functions acting on nonlinear systems wherein the random vector can follow an elliptically symmetric distribution. We provide first and second order differentiability results as well as readily implementable formulæ. We also demonstrate that these formulæ can be readily employed within standard non-linear programming software through a set of illustrative numerical experiments.     

On nonatomicity for non-additive functions

The notion of nonatomicity for set functions plays a key role in classical measure theory and its applications. For classical measures taking values in finite dimensional Banach spaces, it guarantees the connectedness of range. Even just replacing σ-additivity with finite additivity for measures requires some stronger nonatomicity property for the same conclusion to hold. In the present paper, we deal with non-additive functions – called ‘s-outer’ and ‘quasi-triangular’ – defined on rings and taking values in Hausdorff topological spaces. No algebraic structure is required on their target spaces. In this context, we make use of a notion of strong nonatomicity involving just the behavior of functions on ultrafilters of their underlying Boolean domains. This notion is proved to be equivalent to that proposed in earlier contributions concerning Lyapunov-types theorems in additive and non-additive frameworks. Thus, in particular, our analysis allows to generalize, improve and unify several known results on this topic.     

The optical rotatory dispersion of quartz

Many formulæ have been proposed to express numerically the rapid increase of the rotatory power of quartz with decrease of wavelength. An examination of these formulæ shows that they are wholly inappropriate for the case of quartz. It has been shown that the entire range of data from the visible to the extreme ultraviolet is accurately represented by a new type of formula involving only two constants,viz.,

$$\rho = \frac{{k\lambda ^2 }}{{(\lambda ^2 - \lambda _0 ^2 )^2 }},$$     

Volume formula for a ℤ2-symmetric spherical tetrahedron through its edge lengths

The present paper considers volume formulæ, as well as trigonometric identities, that hold for a tetrahedron in 3-dimensional spherical space of constant sectional curvature +1. The tetrahedron possesses a certain symmetry: namely rotation of angle π in the middle points of a certain pair of its skew edges.     

Approaches to measuring inconsistency for stratified knowledge bases

A number of proposals have been proposed for measuring inconsistency for knowledge bases. However, it is rarely investigated how to incorporate preference information into inconsistency measures. This paper presents two approaches to measuring inconsistency for stratified knowledge bases. The first approach, termed the multi-section inconsistency measure (MSIM for short), provides a framework for characterizing the inconsistency at each stratum of a stratified knowledge base. Two instances of MSIM are defined: the naive MSIM and the stratum-centric MSIM. The second approach, termed the preference-based approach, aims to articulate the inconsistency in a stratified knowledge base from a global perspective. This approach allows us to define measures by taking into account the number of formulas involved in inconsistencies as well as the preference levels of these formulas. A set of desirable properties are introduced for inconsistency measures of stratified knowledge bases and studied with respect to the inconsistency measures introduced in the paper. Computational complexity results for these measures are presented. In addition, a simple but explanatory example is given to illustrate the application of the proposed approaches to requirements engineering.     

Some Gaussian binomial sum formulæ with applications

We introduce and compute some Gaussian q-binomial sums formulæ. In order to prove these sums, our approach is to use q-analysis, in particular a formula of Rothe, and computer algebra. We present some applications of our results.     

The logic of justified belief,explicit knowledge,and conclusive evidence

We present a complete, decidable logic for reasoning about a notion of completely trustworthy (“conclusive”) evidence and its relations to justifiable (implicit) belief and knowledge, as well as to their explicit justifications. This logic makes use of a number of evidence-related notions such as availability, admissibility, and “goodness” of a piece of evidence, and is based on an innovative modification of the Fitting semantics for Artemov?s Justification Logic designed to preempt Gettier-type counterexamples. We combine this with ideas from belief revision and awareness logics to provide an account for explicitly justified (defeasible) knowledge based on conclusive evidence that addresses the problem of (logical) omniscience.     

Measuring and repairing inconsistency in probabilistic knowledge bases

In this paper we present a family of measures aimed at determining the amount of inconsistency in probabilistic knowledge bases. Our approach to measuring inconsistency is graded in the sense that we consider minimal adjustments in the degrees of certainty (i.e., probabilities in this paper) of the statements necessary to make the knowledge base consistent. The computation of the family of measures we present here, in as much as it yields an adjustment in the probability of each statement that restores consistency, provides the modeler with possible repairs of the knowledge base. The case example that motivates our work and on which we test our approach is the knowledge base of CADIAG-2, a well-known medical expert system.     

Tarski's theorem on intuitionistic logic,for polyhedra

In 1938, Tarski proved that a formula is not intuitionistically valid if, and only if, it has a counter-model in the Heyting algebra of open sets of some topological space. In fact, Tarski showed that any Euclidean space ${\mathbb{R}}^n$ with $n?1$ suffices, as does e.g. the Cantor space. In particular, intuitionistic logic cannot detect topological dimension in the Heyting algebra of all open sets of a Euclidean space. By contrast, we consider the lattice of open subpolyhedra of a given compact polyhedron $P?{\mathbb{R}}^n$, prove that it is a locally finite Heyting subalgebra of the (non-locally-finite) algebra of all open sets of P, and show that intuitionistic logic is able to capture the topological dimension of P through the bounded-depth axiom schemata. Further, we show that intuitionistic logic is precisely the logic of formulæ valid in all Heyting algebras arising from polyhedra in this manner. Thus, our main theorem reconciles through polyhedral geometry two classical results: topological completeness in the style of Tarski, and Ja?kowski's theorem that intuitionistic logic enjoys the finite model property. Several questions of interest remain open. E.g., what is the intermediate logic of all closed triangulable manifolds?     

Fast and flexible packed string matching

Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. In the last two decades a general trend has appeared trying to exploit the power of the word RAM model to speed-up the performances of classical string matching algorithms. In this model an algorithm operates on words of length w, grouping blocks of characters, and arithmetic and logic operations on the words take one unit of time.In this paper we use specialized word-size packed string matching instructions, based on the Intel streaming SIMD extensions (SSE) technology, to design a very fast string matching algorithm. We evaluate our solution in terms of efficiency, stability and flexibility, where we propose to use the deviation in running time of an algorithm on distinct equal length patterns as a measure of stability.From our experimental results it turns out that, despite their quadratic worst case time complexity, the new presented algorithm becomes the clear winner on the average in many cases, when compared against the most recent and effective algorithms known in literature.     

Overriding subsuming rules

This paper is concerned with intelligent agents that are able to perform nonmonotonic reasoning, not only with, but also about general rules with exceptions. More precisely, the focus is on enriching a knowledge base Γ with a general rule that is subsumed by other rules already there. Such a problem is important because evolving knowledge needs not follow logic as it is well-known from e.g. the belief revision paradigm. However, belief revision is mainly concerned with the case that the extra information logically conflicts with Γ. Otherwise, the extra knowledge is simply doomed to extend Γ with no change altogether. The problem here is different and may require a change in Γ even though no inconsistency arises. The idea is that when a rule is to be added, it might need to override any rule that subsumes it: preemption must take place. A formalism dedicated to reasoning with and about rules with exceptions is introduced. An approach to dealing with preemption over such rules is then developed. Interestingly, it leads us to introduce several implicants concepts for rules that are possibly defeasible.     

Scenario reduction for stochastic programs with Conditional Value-at-Risk

In this paper we discuss scenario reduction methods for risk-averse stochastic optimization problems. Scenario reduction techniques have received some attention in the literature and are used by practitioners, as such methods allow for an approximation of the random variables in the problem with a moderate number of scenarios, which in turn make the optimization problem easier to solve. The majority of works for scenario reduction are designed for classical risk-neutral stochastic optimization problems; however, it is intuitive that in the risk-averse case one is more concerned with scenarios that correspond to high cost. By building upon the notion of effective scenarios recently introduced in the literature, we formalize that intuitive idea and propose a scenario reduction technique for stochastic optimization problems where the objective function is a Conditional Value-at-Risk. Numerical results presented with problems from the literature illustrate the performance of the method and indicate the cases where we expect it to perform well.     

Bilattice logic of epistemic actions and knowledge

Baltag, Moss, and Solecki proposed an expansion of classical modal logic, called logic of epistemic actions and knowledge (EAK), in which one can reason about knowledge and change of knowledge. Kurz and Palmigiano showed how duality theory provides a flexible framework for modeling such epistemic changes, allowing one to develop dynamic epistemic logics on a weaker propositional basis than classical logic (for example an intuitionistic basis). In this paper we show how the techniques of Kurz and Palmigiano can be further extended to define and axiomatize a bilattice logic of epistemic actions and knowledge (BEAK). Our propositional basis is a modal expansion of the well-known four-valued logic of Belnap and Dunn, which is a system designed for handling inconsistent as well as potentially conflicting information. These features, we believe, make our framework particularly promising from a computer science perspective.     

Boolean Valued and Stone Algebra Valued Measure Theories

In conventional generalization of the main results of classical measure theory to Stone algebra valued measures, the values that measures and functions can take are Booleanized, while the classical notion of a σ-field is retained. The main purpose of this paper is to show by abundace of illustrations that if we agree to Booleanize the notion of a σ-field as well, then all the glorious legacy of classical measure theory is preserved completely. Mathematics Subject Classification: 03C90, 28B15.     

Two-weight Hilbert transform and Lipschitz property of Jacobi matrices associated to hyperbolic polynomials

We are going to prove a Lipschitz property of Jacobi matrices built by orthogonalizing polynomials with respect to measures in the orbit of classical Perron-Frobenius-Ruelle operators associated to hyperbolic polynomial dynamics. This Lipschitz estimate will not depend on the dimension of the Jacobi matrix. It is obtained using some sufficient conditions for two-weight boundedness of the Hilbert transform. It has been proved in [F. Peherstorfer, A. Volberg, P. Yuditskii, Limit periodic Jacobi matrices with prescribed p-adic hull and a singular continuous spectrum, Math. Res. Lett. 13 (2-3) (2006) 215-230] for all polynomials with sufficiently big hyperbolicity and in the most symmetric case t=0 that the Lipschitz estimate becomes exponentially better when the dimension of the Jacobi matrix grows. This allows us to get for such polynomials the solution of a problem of Bellissard, in other words, to prove the limit periodicity of the limit Jacobi matrix. We suggest a scheme how to approach Bellissard's problem for all hyperbolic dynamics by uniting the methods of the present paper and those of [F. Peherstorfer, A. Volberg, P. Yuditskii, Limit periodic Jacobi matrices with prescribed p-adic hull and a singular continuous spectrum, Math. Res. Lett. 13 (2-3) (2006) 215-230]. On the other hand, the nearness of Jacobi matrices under consideration in operator norm implies a certain nearness of their canonical spectral measures. One can notice that this last claim just gives us the classical commutative Perron-Frobenius-Ruelle theorem (it is concerned exactly with the nearness of such measures). In particular, in many situations we can see that the classical Perron-Frobenius-Ruelle theorem is a corollary of a certain non-commutative observation concerning the quantitative nearness of pertinent Jacobi matrices in operator norm.     

The generalized Lilbert matrix

We introduce a generalized Lilbert [Lucas-Hilbert] matrix. Explicit formulæ are derived for the LU-decomposition and their inverses, as well as the Cholesky decomposition. The approach is to use q-analysis and to leave the justification of the necessary identities to the q-version of Zeilberger’s celebrated algorithm.