Optimal α-β trees with capacity constraint

Summary We consider a specific kind of binary trees with weighted edges. Each right edge has weight while each left edge has weight . Furthermore, no path in the tree is allowed to contain L or more consecutive -edges, where L 1 is fixed. Given, , , L and the number of nodes n, an optimal tree is one which minimizes the total weighted path length. Algorithms for constructing an optimal tree as well as all optimal trees for given , , L and n are proposed and analyzed. Timing and storage requirements are also discussed.     

Generalized Definite Set Constraints

Set constraints (SC) are logical formulae in which atoms are inclusions between set expressions. Those set expressions are built over a signature , variables and various set operators. On a semantical point of view, the set constraints are interpreted over sets of trees built from and the inclusion symbol is interpreted as the subset relation over those sets. By restricting the syntax of those formulae and/or the set of operators that can occur in set expressions, different classes of set constraints are obtained. Several classes have been proposed and studied for some problems such as satisfiability and entailment. Among those classes, we focus in this article on the class of definite SC's introduced by Heintze and Jaffar, and the class of co-definite SC's studied by Charatonik and Podelski. In spite of their name, those two classes are not dual from each other, neither through inclusion inversion nor through complementation. In this article, we propose an extension for each of those two classes by means of an intentional set construction, so called membership expression. A membership expression is an expression {x| (x)}. The formula (x) is a positive first-order formula built from membership atomst in S in which S is a set expression. We name those two classes respectively generalized definite and generalized co-definite set constraints. One of the main point concerning those so-extended classes is that the two generalized classes turn out to be dual through complementation. First, we prove in this article that generalized definite set constraints is a proper extension of the definite class, as it is more expressive in terms of sets of solutions. But we show also that those extensions preserve some main properties of the definite and co-definite class. Hence for instance, as definite set constraints, generalized definite SC's have a least solution whereas the generalized co-definite SC's have a greatest solution, just as co-definite ones. Furthermore, we devise an algorithm based on tree automata that solves the satisfiability problem for generalized definite set constraints. Due to the dualization, the algorithm solves the satisfiability problem for generalized co-definite set constraints as well. This algorithm proves first that for those generalized classes, the satisfiability problem remains DEXPTIME-complete. It provides also a proof for regularity of the least solution of generalized definite constraints and so, by dualization for the greatest solution for the generalized co-definite SC's.     

Best Huffman trees

Summary Given a sequence of positive weights, W=w ₁...w _n >0, there is a Huffman tree, T (T-up) which minimizes the following functions: max{d(w_i)}; d(w_i); f(d(w_i)) w _i(here d(w _i) represents the distance of a leaf of weight w _i to the root and f is a function defined for nonnegative integers having the property that g(x) = f(x + 1) – f(x) is monotone increasing) over the set of all trees for W having minimal expected length. Minimizing the first two functions was first done by Schwartz [5]. In the case of codes where W is a sequence of probabilities, this implies that the codes based on T have all their absolute central moments minimal. In particular, they are the least variance codes which were also described by Kou [3]. Furthermore, there exists a Huffman tree T, (T-down) which maximizes the functions considered above.However, if g(x) is monotone decreasing, T and T, respectively maximize and minimize f(d(w_i) w _i) over the set of all trees for W having minimal expected length. In addition, we derive a number of interesting results about the distribution of labels within Huffman trees. By suitable modifications of the usual Huffman tree construction, (see [1]) T and T can also be constructed in time O(n log n).     

Linear scale-space

The formulation of afront-end orearly vision system is addressed, and its connection with scale-space is shown. A front-end vision system is designed to establish a convenient format of some sampled scalar field, which is suited for postprocessing by various dedicated routines. The emphasis is on the motivations and implications of symmetries of the environment; they pose natural, a priori constraints on the design of a front-end.The focus is on static images, defined on a multidimensional spatial domain, for which it is assumed that there are no a priori preferred points, directions, or scales. In addition, the front-end is required to be linear. These requirements are independent of any particular image geometry and express the front-end's pure syntactical, bottom up nature.It is shown that these symmetries suffice to establish the functionality properties of a front-end. For each location in the visual field and each inner scale it comprises a hierarchical family of tensorial apertures, known as the Gaussian family, the lowest order of which is the normalised Gaussian. The family can be truncated at any given order in a consistent way. The resulting set constitutes a basis for alocal jet bundle. Note that scale-space theory shows up here without any call upon the prohibition of spurious detail, which, in some way or another, usually forms the basic starting point for diffusion-like scale-space theories.     

One Connection between Standard Invariance Conditions on Modal Formulas and Generalized Quantifiers

The language of standard propositional modal logic has one operator ( or ), that can be thought of as being determined by the quantifiers or , respectively: for example, a formula of the form is true at a point s just in case all the immediate successors of s verify .This paper uses a propositional modal language with one operator determined by a generalized quantifier to discuss a simple connection between standard invariance conditions on modal formulas and generalized quantifiers: the combined generalized quantifier conditions of conservativity and extension correspond to the modal condition of invariance under generated submodels, and the modal condition of invariance under bisimulations corresponds to the generalized quantifier being a Boolean combination of and .     

Obvious inferences

The notion of obvious inference in predicate logic is discussed from the viewpoint of proof-checker applications in logic and mathematics education. A class of inferences in predicate logic is defined and it is proposed to identify it with the class of obvious logical inferences. The definition is compared with other approaches. The algorithm for implementing the obviousness decision procedure follows directly from the definition.     

On the growth factor in Gaussian elimination for matrices with sharp angular field of values

Abstract Recently, the authors have shown that Gaussian elimination is stable for complex matrices A=B+iC where both B and C are Hermitian definite matrices. Moreover, the growth factor is less than under any diagonal pivoting order. Assume now that B and C, in addition to being (positive) definite, satisfy the inequality i.e., If = 0, then A = B is a Hermitian positive definite matrix. It is well-known that, in this case, the growth factor is equal to 1. For > 0, we establish a bound for the growth factor that has the limit 1 as 0.     

Information and Meaning: Use-Based Models in Arrays of Neural Nets

The goal of philosophy of information is to understand what information is, how it operates, and how to put it to work. But unlike information in the technical sense of information theory, what we are interested in is meaningful information. To understand the nature and dynamics of information in this sense we have to understand meaning. What we offer here are simple computational models that show emergence of meaning and information transfer in randomized arrays of neural nets. These we take to be formal instantiations of a tradition of theories of meaning as use. What they offer, we propose, is a glimpse into the origin and dynamics of at least simple forms of meaning and information transfer as properties inherent in behavioral coordination across a community.     

Trace nets and process automata

Trace nets are a variant of one-safe Petri nets, where input and output places may be filled as well as emptied by transitions. Those extended nets are introduced for modelling concurrency in a simple format of structural operational specifications, based on permutation of proved transitions. Trace nets are connected by an adjunction to a particular class of trace automata in the sense of Stark, namely the separated trace automata. The adjunction is based on a calculus of regions that differ significantly from the ones devised by Ehrenfeucht and Rozenberg for elementary nets, although the axioms of separation are the same.This work was partly supported by the project MASK of the E.C. Program Science.     

On the height of digital trees and related problems

This paper studies in a probabilistic framework some topics concerning the way words (strings) can overlap, and relationship of this to the height of digital trees associated with this set of words. A word is defined as a random sequence of (possibly infinite) symbols over a finite alphabet. A key notion of analignment matrix {C _ij } _i,j=1 ⁿ is introduced whereC _ij is the length of the longest string that is a prefix of theith and thejth word. It is proved that the height of an associated digital tree is simply related to the alignment matrix through some order statistics. In particular, using this observation and proving some inequalities for order statistics, we establish that the height of adigital trie under anindependent model (i.e., all words are statistically independent) is asymptotically equal to 2 log n wheren is the number of words stored in the trie and is a parameter of the probabilistic model. This result is generalized in three directions, namely we considerb-tries,Markovian model (i.e., dependency among letters in a word), and adependent model (i.e., dependency among words). In particular, when consecutive letters in a word are Markov dependent (Markovian model), then we demonstrate that the height converges in probability to 2 log n where is a parameter of the underlying Markov chain. On the other hand, for suffix trees which fall into the dependent model, we show that the height does not exceed 2 log n, where is a parameter of the probabilistic model. These results find plenty of applications in the analysis of data structures built over digital words.This research was supported by NSF Grants NCR-8702115 and CCR-8900305, in part by Grant R01 LM05118 from the National Library of Medicine, and by AFOSR Grant 90-0107.