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.     

A Delay-Averaged Logistic Model

For the equation x(t) = x(t) (1-(1/) _t-- ^t- x(u)du), > 0, > 0, > 0, conditions for the stability of a nonzero stationary solution under small perturbations are determined.     

A faster divide-and-conquer algorithm for constructing delaunay triangulations

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its (n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn2¹⁶, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL _p metric for 1<p.This research was supported by National Science Foundation Grants DCR-8352081 and DCR-8416190.     

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     

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.     

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.     

Three ∑ P 2 -complete problems in computational learning theory

The consistency problem associated with a concept classC is to determine, given two setsA andB of examples, whether there exists a conceptc inC such that eachx inA is a positive example ofc and eachy inB is a negative example ofc. We explore in this paper the following intuition: for a concept classC, if the membership problem of determining whether a given example is positive for a concept isNP-complete, then the corresponding consistency problem is likely to be _P ² -complete. To support this intuition, we prove that the following three consistency problems for concept classes of patterns, graphs and generalized Boolean formulas, whose membership problems are known to beNP-complete, are _P ² -complete: (a) given two setsA andB of strings, determine whether there exists a patternp such that every string inA is in the languageL(p) and every string inB is not in the languageL(p); (b) given two setsA andB of graphs, determine whether there exists a graphG such that every graph inA is isomorphic to a subgraph ofG and every graph inB is not isomorphic to any subgraph ofG; and (c) given two setsA andB of Boolean formulas, determine whether there exists a 3-CNF Boolean formula such that for every A, is satisfiable and for every B, is not satisfiable. These results suggest that consistendy problems in machine learning are natural candidates for _P ² -complete problems if the corresponding membership problems are known to beNP-complete.In addition, we prove that the corresponding prediction problems for concept classes of polynomial-time nondeterministic Turing machines, nondeterministic Boolean circuits, generalized Boolean formulas, patterns and graphs are prediction-complete for the classR _NP of all concept classes whose membership problems are inNP.     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.     

How to find Steiner minimal trees in euclideand-space

This paper has two purposes. The first is to present a new way to find a Steiner minimum tree (SMT) connectingN sites ind-space,d >- 2. We present (in Appendix 1) a computer code for this purpose. This is the only procedure known to the author for finding Steiner minimal trees ind-space ford > 2, and also the first one which fits naturally into the framework of backtracking and branch-and-bound. Finding SMTs of up toN = 12 general sites ind-space (for anyd) now appears feasible.We tabulate Steiner minimal trees for many point sets, including the vertices of most of the regular and Archimedeand-polytopes with <- 16 vertices. As a consequence of these tables, the Gilbert-Pollak conjecture is shown to be false in dimensions 3–9. (The conjecture remains open in other dimensions; it is probably false in all dimensionsd withd 3, but it is probably true whend = 2.)The second purpose is to present some new theoretical results regarding the asymptotic computational complexity of finding SMTs to precision .We show that in two-dimensions, Steiner minimum trees may be found exactly in exponential time O(C ^N ) on a real RAM. (All previous provable time bounds were superexponential.) If the tree is only wanted to precision , then there is an (N/)^O(N)-time algorithm, which is subexponential if 1/ grows only polynomially withN. Also, therectilinear Steiner minimal tree ofN points in the plane may be found inN ^O(N) time.J. S. Provan devised an O(N ⁶/⁴)-time algorithm for finding the SMT of a convexN-point set in the plane. (Also the rectilinear SMT of such a set may be found in O(N ⁶) time.) One therefore suspects that this problem may be solved exactly in polynomial time. We show that this suspicion is in fact true—if a certain conjecture about the size of Steiner sensitivity diagrams is correct.All of these algorithms are for a real RAM model of computation allowing infinite precision arithmetic. They make no probabilistic or other assumptions about the input; the time bounds are valid in the worst case; and all our algorithms may be implemented with a polynomial amount of space. Only algorithms yielding theexact optimum SMT, or trees with lengths (1 + ) × optimum, where is arbitrarily small, are considered here.     

Reasoning about programs in continuation-passing style

Plotkin's _v -calculus for call-by-value programs is weaker than the -calculus for the same programs in continuation-passing style (CPS). To identify the call-by-value axioms that correspond to on CPS terms, we define a new CPS transformation and an inverse mapping, both of which are interesting in their own right. Using the new CPS transformation, we determine the precise language of CPS terms closed under -transformations, as well as the call-by-value axioms that correspond to the so-called administrative -reductions on CPS terms. Using the inverse mapping, we map the remaining and equalities on CPS terms to axioms on call-by-value terms. On the pure (constant free) set of -terms, the resulting set of axioms is equivalent to Moggi's computational -calculus. If the call-by-value language includes the control operatorsabort andcall-with-current-continuation, the axioms are equivalent to an extension of Felleisenet al.'s _v -C-calculus and to the equational subtheory of Talcott's logic IOCC.This article is a revised and extended version of the conference paper with the same title [42]. The technical report of the same title contains additional material.The authors were supported in part by NSF grant CCR 89-17022 and by Texas ATP grant 91-003604014.     

Determining literariness in interactive fiction

The authors of interactive fiction are beginning to demonstrate a concern for the literariness of their product. Literariness, as defined by Shklovskij and the Russian Formalists, is the quality of making strange that which is linguistically familiar, a quality Shklovskij termed ostranenie. By applying the principle of ostranenie, as well as other well-known literary principles, to the most serious interactive fictions, we can determine if this new genre exhibits the features of literariness. A study of Mindwheel, Brimstone, Breakers, A Mind Forever Voyaging, Portal, and Trinity suggest that the literariness of interactive fiction comes out of its concern both for making strange what is familiar and for making familiar what is strange.Neil Randall has published several role-playing games, and is working on a full-length critical study of interactive fiction. He is currently assistant professor of English.     

Specification and verification of database dynamics

Summary A framework is proposed for the structured specification and verification of database dynamics. In this framework, the conceptual model of a database is a many sorted first order linear tense theory whose proper axioms specify the update and the triggering behaviour of the database. The use of conceptual modelling approaches for structuring such a theory is analysed. Semantic primitives based on the notions of event and process are adopted for modelling the dynamic aspects. Events are used to model both atomic database operations and communication actions (input/output). Nonatomic operations to be performed on the database (transactions) are modelled by processes in terms of trigger/reaction patterns of behaviour. The correctness of the specification is verified by proving that the desired requirements on the evolution of the database are theorems of the conceptual model. Besides the traditional data integrity constraints, requirements of the form Under condition W, it is guaranteed that the database operation Z will be successfully performed are also considered. Such liveness requirements have been ignored in the database literature, although they are essential to a complete definition of the database dynamics.

Notation

Classical Logic Symbols (Appendix 1) for all (universal quantifier) - exists at least once (existential quantifier) - ¬ no (negation) - implies (implication) - is equivalent to (equivalence) - and (conjunction) - or (disjunction) Tense Logic Symbols (Appendix 1) G always in the future - G ₀ always in the future and now - F sometime in the future - F ₀ sometime in the future or now - H always in the past - H ₀ always in the past and now - P sometime in the past - P ₀ sometime in the past or now - X in the next moment - Y in the previous moment - L always - M sometime Event Specification Symbols (Sects. 3 and 4.1) (x) means immediately after the occurrence of x - (x) means immediately before the occurrence of x - (x) means x is enabled, i.e., x may occur next - { } ({w ₁} x{w ₂}) states that if w ₁ holds before the occurrence of x, then w ₂ will hold after the occurrence of x (change rule) - [ ] ([oa₁, ..., oa_n]x) states that only the object attributes oa₁, ..., oa _n are modifiable by x (scope rule) - {{ }} ({{w}}x) states that if x may occur next, then w holds (enabling rule) Process Specification Symbols (Sects. 5.3 and 5.4) :: for causal rules - for behavioural rules Transition-Pattern Composition Symbols (Sects. 5.2 and 5.3) ; sequential composition - ¦ choice composition - parallel composition - :| guarded alternative composition Location Predicates (Sect. 5.2) (z) means immediately after the occurrence of the last event of z (after) - (z) means immediately before the occurrence of the first event of z (before) - (z) means after the beginning of z and before the end of z (during) - ( z) means before the occurrence of an event of z (at)     

Conditions for the Light-Traffic Insensitivity to Loss Probability in a GI/G/m/0 Queueing System

A loss queueing system GI/G/m/0 is considered. Let a(x) be a p.d.f. of interarrival intervals. Assume that this function behaves like cx^-1 for small x. Further let B(x) be a d.f. of service time; (1/) be the mean service time. Conditions are derived for the light-traffic insensitivity of the loss probability to the form of B(x) as (/ ) 0. In particular, the condition = 1 is necessary. Estimates for the loss probability are obtained.     

Cardinality problems of compositions of morphisms and inverse morphisms

We show that we cannot effectively determine whether, for morphisms _i , _i ,card (u ₀ ^–1 ₁) =card(u ₀ ^–1 ₁) for all wordsu over the domain alphabets of the two given compositions. In contrast it is decidable for morphisms _i , _i and a regular setR whethercard(u _{0 1} ^–1 ) =card(u _{0 1} ^–1 ) for all wordsu inR. In order to prove the latter result we give a characterization of the multiplicity functions of simple finite automata by using cardinalities of compositions of the above form. Finally, we show that the above decidability result also holds when we consider rational functions rather than morphisms.     

States and the free orthogonality monoid

Let (X, #) be an orthogonality space such that the lattice C(X, #) of closed subsets of (X, #) is orthomodular and let (, ) denote the free orthogonality monoid over (X, #). Let C₀(, ) be the subset of C(, ), consisting of all closures of bounded orthogonal sets. We show that C₀(, ) is a suborthomodular lattice of C(, ) and we provide a necessary and sufficient condition for C₀(, ) to carry a full set of dispersion free states.The work of the second author on this paper was supported by National Science Foundation Grant GP-9005.     

The mixing properties of certain processes related to Markov chains

Summary Let {Y _n ,– < n < } be either a function of a stationary Markov chain with countable state space, or a finitary process in the sense of Heller [3]. The purpose of this note is to prove that if {Y _n ,– < n < } is mixing, then it is aK-shift. (Definitions will be given below.)IfT is a measure-preserving transformation on a probability space, then the following implications relevant to the present paper are known: (1)T is aK-shift T is (r + 1)-mixing T isr-mixing T is totally ergodic T is ergodic, and (2)T is ergodic T is totally ergodic T isr-mixing T is aK-shift.It is not known if the classes ofr-mixing and (r + 1)-mixing transformations are distinct. (1-mixing is also called mixing.) The results of this note then imply that for the classes of transformation that we are consideringr-mixing and (r + 1)-mixing are equivalent.This research was partially supported by NSF Grant GP-19660.     

Local determinacy of abstract local dynamical systems

O. Hájek proved in his book Dynamical Systems in the Plane (Chapter III) that there isat most one abstract local dynamical system which is locally equivalent to, or equivalently an extension of, a given elementary dynamical system, and suggested a question of finding reasonable conditions on the latter for the existence ofat least one such abstract local dynamical system. An elementary dynamical system is said to satisfy the No-Intersection Axiom and is called an abstract germ if(x ₁, t) = (x ₂,t) impliesx ₁ =x ₂. We show that is (uniquely) extendable to an abstract local dynamical system if and only if is an abstract germ, and hence the question is completely answered. After introducing various kinds of isomorphisms of abstract germs and abstract local dynamical systems corresponding to those of continuous germs and continuous local dynamical systems, we obtain some sufficient conditions for extendability of isomorphisms and possibility of restriction of them, and thus establish the local determinacy of abstract local dynamical systems up to isomorphisms in some wider categories.Dedicated to Professor Yusuke HAGIHARA in Commemoration of His Seventy-Seventh Anniversary     

Efficient Solution of Multi-Term Fractional Differential Equations Using P(EC)<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>E Methods

We investigate strategies for the numerical solution of the initial value problem with initial conditions where 0<₁<₂<<. Here y ⁽ _j ) denotes the derivative of order _j >0 (not necessarily _j ) in the sense of Caputo. The methods are based on numerical integration techniques applied to an equivalent nonlinear and weakly singular Volterra integral equation. The classical approach leads to an algorithm with very high arithmetic complexity. Therefore we derive an alternative that leads to lower complexity without sacrificing too much precision. Mathematics Subject Classification: Primary 65L05; Secondary 65L06, 65L20     

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]).     

Thek-server dual and loose competitiveness for paging

Weighted caching is a generalization ofpaging in which the cost to evict an item depends on the item. We study both of these problems as restrictions of the well-knownk-server problem, which involves moving servers in a graph in response to requests so as to minimize the distance traveled.We give a deterministic on-line strategy for weighted caching that, on any sequence of requests, given a cache holdingk items, incurs a cost within a factor ofk/(k–h+1) of the minimum cost possible given a cache holdingh items. The strategy generalizes least recently used, one of the best paging strategies in practice. The analysis is a primal-dual analysis, the first for an on-line problem, exploiting the linear programming structure of thek-server problem.We introduceloose competitiveness, motivated by Sleator and Tarjan's complaint [ST] that the standard competitive ratios for paging strategies are too high. Ak-server strategy isloosely c(k)-competitive if, for any sequence, foralmost all k, the cost incurred by the strategy withk serverseither is no more thanc(k) times the minimum costor is insignificant.We show that certain paging strategies (including least recently used, and first in first out) that arek-competitive in the standard model are looselyc(k)-competitive providedc(k)/Ink and bothk/c(k) andc(k) are nondecreasing. We show that the marking algorithm, a randomized paging strategy that is (Ink)-competitive in the standard model, is looselyc(k)-competitive providedk–2 In Ink and both 2 Ink–c(k) andc(k) are nondecreasing.This paper is the journal version of On-line Caching as Cache Size Varies, which appeared in theProceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (1991). Details beyond those in this paper may be found in Competitive Paging and Dual-Guided Algorithms for Weighted Caching and Matching, which is the author's thesis and is available as Technical Report CS-TR-348-91 from the Computer Science Department at Princeton University.This research was performed while the author was at the Computer Science Department, Princeton University, Princeton, NJ 08544, USA, and was supported by the Hertz Foundation.