Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.     

A Modular Algorithm for Computing Cohomologies of Lie Algebras and Superalgebras

The paper describes an improved algorithm for computing cohomologies of Lie (super)algebras. The original algorithm developed earlier by the author of this paper is based on the decomposition of the entire cochain complex into minimal subcomplexes. The suggested improvement consists in the replacement of the arithmetic of rational or integer numbers by a more efficient arithmetic of modular fields and the use of the relationship dim H ^k( _p) dimH ^k() between the dimensions of cohomologies over an arbitrary modular field _p = /p and the filed of rational numbers . This inequality allows us to rapidly find subcomplexes for which dimH ^k( _p) > 0 (the number of such subcomplexes is usually not great) using computations over an arbitrary _p and, then, carry out all required computations over in these subcomplexes.     

On the Noninteger Polyhedron Vertices of the Three-index Axial Transportation Problem

For the three-index axial transportation polyhedron defined by the integer vector, existence of noninteger vertices was proved. In particular, the three-index n × m × k axial transportation polyhedron having vertices with r fractional components was shown to exist for and only for any number r {4,6,7,...,(n, m, k)}, where (n, m, k) = min{n, m + k - 2} + m + k - 2, n m k 3.     

Optimal multilayer channel routing with overlap

This paper presents algorithms for multiterminal net channel routing where multiple interconnect layers are available. Major improvements are possible if wires are able to overlap, and our generalized main algorithm allows overlap, but only on everyKth (K 2) layer. Our algorithm will, for a problem with densityd onL layers,L K + 3,provably use at most three tracks more than optimal: (d + 1)/L/K + 2 tracks, compared with the lower bound of d/L/K. Our algorithm is simple, has few vias, tends to minimize wire length, and could be used if different layers have different grid sizes. Finally, we extend our algorithm in order to obtain improved results for adjacent (K = 1) overlap: (d + 2)/2L/3 + 5 forL 7.This work was supported by the Semiconductor Research Corporation under Contract 83-01-035, by a grant from the General Electric Corporation, and by a grant at the University of the Saarland.     

Linear Interval Tolerance Problem and Linear Programming Techniques

In this paper, we consider the linear interval tolerance problem, which consists of finding the largest interval vector included in ([A], [b]) = {x R ⁿ | A [A], b [b], Ax = b}. We describe two different polyhedrons that represent subsets of all possible interval vectors in ([A], [b]), and we provide a new definition of the optimality of an interval vector included in ([A], [b]). Finally, we show how the Simplex algorithm can be applied to find an optimal interval vector in ([A], [b]).     

Mesh Selection for a Nearly Singular Boundary Value Problem

In this paper, we investigate the numerical solution of a model equation u _xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.     

Context-free text grammars

A text is a triple=(, ₁, ₂) such that is a labeling function, and ₁ and ₂ are linear orders on the domain of ; hence may be seen as a word (, ₁) together with an additional linear order ₂ on the domain of . The order ₂ is used to give to the word (, ₁) itsindividual hierarchical representation (syntactic structure) which may be a tree but it may be also more general than a tree. In this paper we introducecontext-free grammars for texts and investigate their basic properties. Since each text has its own individual structure, the role of such a grammar should be that of a definition of a pattern common to all individual texts. This leads to the notion of ashapely context-free text grammar also investigated in this paper.     

Logic Based Abstractions of Real-Time Systems

When verifying concurrent systems described by transition systems, state explosion is one of the most serious problems. If quantitative temporal information (expressed by clock ticks) is considered, state explosion is even more serious. We present a notion of abstraction of transition systems, where the abstraction is driven by the formulae of a quantitative temporal logic, called qu-mu-calculus, defined in the paper. The abstraction is based on a notion of bisimulation equivalence, called , n-equivalence, where is a set of actions and n is a natural number. It is proved that two transition systems are , n-equivalent iff they give the same truth value to all qu-mu-calculus formulae such that the actions occurring in the modal operators are contained in , and with time constraints whose values are less than or equal to n. We present a non-standard (abstract) semantics for a timed process algebra able to produce reduced transition systems for checking formulae. The abstract semantics, parametric with respect to a set of actions and a natural number n, produces a reduced transition system , n-equivalent to the standard one. A transformational method is also defined, by means of which it is possible to syntactically transform a program into a smaller one, still preserving , n-equivalence.     

Choosing reference classes and building provisional models

A well-known problem in default logic is the ability of naive reasoners to explain bothg and ¬g from a set of observations. This problem is treated in at least two different ways within that camp.One approach is examination of the various explanations and choosing among them on the basis of various explanation comparators. A typical comparator is choosing the explanation that depends on the most specific observation, similar to the notion of narrowest reference class.Others examine default extensions of the observations and choose whatever is true in any extension, or what is true in all extensions or what is true in preferred extensions. Default extensions are sometimes thought of as acceptable models of the world that are discarded as more knowledge becomes available.We argue that the notions of specificity and extension lack clear semantics. Furthermore, we show that the problems these ideas were supposed to solve can be handled easily within a probabilistic framework.     

Cut point languages of markov DTOL systems

Letp satisfy 0 p < 1, then by (p) we denote the family of Markov DTOL languages with cut pointp. In this paper we present a complete classification of the collection of such families (p), 0 p < 1, showing that forms an infinite nondense hierarchy with (0) being its only accumulation point from below. Furthermore it is proved that each language in (p) can be expressed as a finite union of DDTOL languages.Work supported partially by the Natural Sciences and Engineering Research Council of Canada grants Nos. A-3590 and A-7700, and partially by Deutsche Forschungsgemeinschaft.     

On Steiner minimal trees withLp distance

LetL _p be the plane with the distanced _p (A ₁ ,A ₂ ) = (¦x ₁ –x ₂¦ ^p + ¦y₁ –y ₂¦^p)^/1p wherex _i andy _i are the cartesian coordinates of the pointA _i . LetP be a finite set of points inL _p . We consider Steiner minimal trees onP. It is proved that, for 1 <p < , each Steiner point is of degree exactly three. Define the Steiner ratio _p to be inf{L _s (P)/L _m (P)¦PL _p } whereL _s (P) andL _m (P) are lengths of the Steiner minimal tree and the minimal spanning tree onP, respectively. Hwang showed ₁ = 2/3. Chung and Graham proved ₂ > 0.842. We prove in this paper that {} = 2/3 and (2/2)_{12 p} 3/2 for anyp.This work was supported in part by the National Science Foundation of China and the President Foundation of Academia Sinica.     

Randomized vs. deterministic decision tree complexity for read-once Boolean functions

We consider the deterministic and the randomized decision tree complexities for Boolean functions, denotedDC(f) andRC(f), respectively. A major open problem is how smallRC(f) can be with respect toDC(f). It is well known thatRC(f)DC(f) ^0.5 for every Boolean functionf (called 0.5-exponent). On the other hand, some Boolean functionf is known to haveRC(f) = (DC(f))^0.753...) (or 0.753...-exponent). It is not known whether there is a Boolean function with exponent smaller than 0.753... Likewise, no lower bound for arbitrary Boolean functions with exponent greater than 0.5 is known.Our result is a 0.51 lower bound on the exponent for everyread-once function. Read-once means that each input variable appears exactly once in the Boolean formula representing the function. To obtain this result we generalize an existing lower bound technique and combine it with restriction arguments. This result provides a lower bound ofn ^0.51 on the number of positions that have to be evaluated by any randomized - pruning algorithm computing the value of any two-person zero-sum game tree withn final positions.     

Indecomposable local maps of tessellation automata

Indecomposable local maps of one-dimensional tessellation automata are studied. The main results of this paper are the following. (1) For any alphabet containing two or more symbols and for anyn 1, there exist indecomposable scope-n local maps over . (2) If is a finite field of prime order, then a linear scope-n local map over is indecomposable if and only if its associated polynomial is an irreducible polynomial of degreen – 1 over , except for a trivial case. (3) Result (2) is no longer true if is a finite field whose order is not prime.     

The conjoinability relation in Lambek calculus and linear logic

In 1958 J. Lambek introduced a calculusL of syntactic types and defined an equivalence relation on types: x y means that there exists a sequence x=x₁,...,x_n=y (n 1), such thatx _i x _i+1 or x_i+ x _i (1 i n). He pointed out thatx y if and only if there is joinz such thatx z andy z. This paper gives an effective characterization of this equivalence for the Lambeck calculiL andLP, and for the multiplicative fragments of Girard's and Yetter's linear logics. Moreover, for the non-directed Lambek calculusLP and the multiplicative fragment of Girard's linear logic, we present linear time algorithms deciding whether two types are equal, and finding a join for them if they are.The author was sponsored by project NF 102/62-356 (Structural and Semantic Parallels in Natural Languages and Programming Languages), funded by the Netherlands Organization for the Advancement of Research (N.W.O.).     

Hierarchies of polynomially solvable satisfiability problems

In this paper, we introduce general techniques for extending classes of polynomially solvable SAT instances. We generalize the approach of Gallo and Scutellà, who defined the hierarchy { _i }, where _l corresponds to the Generalized Horn class. We propose a family of polynomial hierarchies, where a polynomial hierarchy { _i } is a sequence of polynomially solvable classes that cover the whole set of CNF formulas, and such that _{i i+1} fori0. Following a different approach, based on a new decomposition technique, we define the class of Split-Horn formulas, which is an extension of _l. We discuss and compare the basic properties of the proposed classes; polynomial time algorithms for recognition and solution are provided.     

A short note on simultaneous splitting

We show that for any alphabet there is a setL ^* such that ifC is any infinite co-infinite context-free language over , thenL splitsC (i.e., each ofL C,L , C, and is infinite).Preparation of this paper was supported in part by the National Science Foundation under Grant No. MCS77-11360.     

Mathematical and statistical details on the simulation of MARKOFF-Type stochastic processes on an electronic computer

Summary This paper deals with the generation of stationaryp ^th order linear autoregressive series (calledM _p -series) on an electronic computer. The interrelations between the coefficients of autocorrelation are discussed and a device and a flow diagram are given for the generation ofM _p -series which possess the autocorrelation coefficients ₁, ₂,... _p . The conclusion is that there is anM _p -series for a given set of values only if there is anM _q -series for any subset ₁,... _q withq=1,2,...q–1 and that, conversely, if there is anM _p -series for given ₁,₂,... _p , there is also anM _q -series with ₁,... _q for 1q<p.The series withp=1, 2, 3 are treated fully and numerical examples forp=1 andp=2 are given in Fig. 4.

---

Zusammenfassung In diesem Aufsatz wird besprochen wie mit Hilfe einer elektronischen Rechenmaschine stationäre lineare autoregressive Reihen der Ordnungp (M _p -Reihen genannt) konstruiert werden können. Nachdem die Beziehungen zwischen den Autokorrelationskoeffizienten abgeleitet worden sind, wird ein Schema und ein Flußdiagramm zur Erzeugung vonM _p -Reihen gegeben, die vorgegebene Autokorrelationskoeffizienten ₁,... _p besitzen. Das Ergebnis lautet: EineM _p -Reihe für eine Gruppe von gegebenen Werten ₁,... _p ist nur möglich, wenn eineM _q -Reihe für jede Untergruppe ₁,... _q mitq=1, 2, ...p–1 möglich ist. Wenn einmal eineM _p -Reihe mit gegebenen ₁,... _p existiert, dann existiert ebenfalls jedeM _q -Reihe mit ₁,... _q , wobei 1q<p ist.Die Fällep=1, 2, 3 werden ausführlich behandelt, während die Abb. 4 numerische Beispiele fürp=1 undp=2 zeigt.

---

---

With 4 Figures     

From Conditional Events to Conditional Measures: A New Axiomatic Approach

Our starting point is a definition of conditional event EH which differs from many seemingly similar ones adopted in the relevant literature since 1935, starting with de Finetti. In fact, if we do not assign the same third value u (undetermined) to all conditional events, but make it depend on EH, it turns out that this function t(EH) can be taken as a general conditional uncertainty measure, and we get (through a suitable – in a sense, compulsory – choice of the relevant operations among conditional events) the natural axioms for many different (besides probability) conditional measures.     

Deterministic sequential functions

The simple rational partial functions accepted by generalized sequential machines are shown to coincide with the compositions _P ^–1 , where _P consists of the prefix codings. The rational functions accepted by generalized sequential machines are proved to coincide with the compositions _P ^–1 , where is the family of endmarkers and is the family of removals of endmarkers. (The compositions are read from left to right). We also show that _P ^–1 is the family of the subsequential functions.This work was partially supported by the Esprit Basic Research Action Working Group No. 3166 ASMICS, the CNRS and the Academy of Finland     

Utilizing deontic operators in information systems specification

One major task in requirements specification is to capture the rules relevant to the problem at hand. Declarative, rule-based approaches have been suggested by many researchers in the field. However, when it comes to modeling large systems of rules, not only for the behavior of the computer system but also for the organizational environment surrounding it, current approaches have problems with limited expressiveness, flexibility, and poor comprehensibility. Hence, rule-based approaches may benefit from improvements in two directions: (1) improvement of the rule languages themselves and (2) better integration with other, complementary modeling approaches.In this article, both issues are addressed in an integrated manner. The proposal is presented in the context of the Tempora project on rule-based information systems development, but has also been integrated with PPP. Tempora has provided a rule language based on an executable temporal logic working on top of a temporal database. The rule language is integrated with static (ER-like) and dynamic (SA/RT-like) modeling approaches. In the current proposal, the integration with complementary modeling approaches is extended by including organization modeling (actors, roles), and the expressiveness of the rule language is increased by introducing deontic operators and rule hierarchies. The main contribution of the article is not seen as any one of the above-mentioned extensions, but as the resulting comprehensive modeling support. The approach is illustrated by examples taken from an industrial case study done in connection with Tempora.C. List of Symbols Subset of set - Not subset of set - Element of set - Not element of set - Equivalent to - Not equivalent to - ¬ Negation - Logical and - Logical or - Implication - Sometime in past - Sometime in future - Always in past - Always in future - Just before - Just after - u Until - s Since - Trigger - Condition - _s State condition - Consequence - _a Action - _s State - Role - Actor - ¬ - General deontic operator - O Obligatory - R Recommended - P Permitted - D Discouraged - F Forbidden - (/–) General rule - t _R Real time - t _M Model time