12975927
Uniform Interpretations of L Forms
This paper investigates interpretations of L forms in which the substitution defining the interpretation is uniform in terminal letters. Such uniform interpretations have several advantages over the ordinary ones, both from a mathematical and biological point of view. A number of different aspects of uniform interpretations are studied. It is felt that the results will shed new light on the theory of L forms and, in general, on the theory of L systems.
30874363
Synchronized EOL Forms Under Uniform Interpretation
— The aim ofthis paper is thejurther study oj EOLjorms under uniform interprétation. We are naturally led to the considération oj synchronized EOLjorms, which become the central thème of this paper. We prove: a ""strongest"" possible normaljorm resuit, the spanning normalJorm theorem; the non-existence oj uni-generatorsjor "reasonable" language amilies, which include thefinite, regular and context-jree j amilies; and a char act erization oj those ynchronized jorms which, under uniform interprétation, yield all regular languages. In closing we remark on three topics which are worthy oj separate investigation. Résumé. — Le but de cet article est de poursuivre l'étude des EOL-jormes sous des interprétations unijormes. Nous sommes conduits naturellement à considérer les EOL-jormes synchronisées qui deviennent le thème central de cet article. Nous établissons : un résultat sur la forme normale la plus « serrée » possible, le théorème sur la forme normale recouvrante, la non-existence d'uni-générateurs pour des jamilles « raisonnables » de langages qui comprennent les langages finis, rationnels et algébriques; et une caractérisation des formes synchronisées qui donnent, par interprétation unijorme, tous les langages rationnels. Pour terminer, nous effleurons trois domaines qui méritent une étude séparée.
7533318
Completeness of Context-Free Grammar Forms
The notions of a grammar form and g-interpretation were first introduced in [2]. However, it quickly became apparent, particularly for EOL forms [5], that (strict) interpretations had a wider interest as well as being better motivated mathematically. The study of parsing of grammar forms detailed in [4], the basic investigation in [8] on linear completeness amongst other results, the study of density in [9, lo] and the connections with graph theory shown in [ 1 l] have affirmed this position. The present paper continues the approach of [8] focussing on the characterization of complete grammar forms, that is grammar forms which generate all’ context-free languages. Some decidability problems will also be discussed. For further morivation and background material we refer the reader to [8, 141, while for all unexplained concepts in language theory, see [ 131. After giving the necessary definitions in the remainder of this section we characterize complete grammar forms in Section 2, 3 and 4. In Section 2 we introduce the central concept of expansion spectrum and in Section 3 the recently proved super normal form theorem [ 121, while in Section 4 the characterization is completed and generators and hierarchies are briefly mentioned. Consider context-free grammars G = (V, C, P, S), where Z is the alphabet of terminals, VZ the alphabet of nonterminals, P is the set of productions and
21847551
Bounded Delay L Codes
Abstract Three natural notions of bounded delay for L codes are investigated. All interrelations, many of them rather surprising, between ordinary codes of bounded delay and L codes of bounded delay of various types are established.
12582971
Stabbing line segments
An algorithm for the geometric problem of determining a line (called a stabbing line) which intersects each ofn given line segments in the plane is presented. As a matter of fact, the algorithm computes a description of all stabbing lines. A purely geometric fact is proved which infers that this description requiresO(n) space to be specified. Our algorithm computes it inO(n logn) time which is optimal in the worst case.Using the description of the stabbing lines, we are able to decide inO(logn) time whether or not a specified line is a stabbing line. Finally, the problem of maintaining the description of all stabbing lines while inserting and deleting line segments is addressed.
33163861
Finitary and infinitary interpretations of languages
The main result of the paper can be viewed both as a generalization of a classical results concerning colorings of graphs, as well as a very useful over-all theorem from which various specific results concerning grammar and language families can be deduced. Essentially our main result says that, when considering infinitary families obtainable by inverse morphisms, it suffices to consider their finitary parts. Various applications are given, in particular, to grammar forms and context-free languages over infinite alphabets.
8780088
Dimension-Exchange Algorithms for Load Balancing on Trees
This paper considers dimension-exchange algorithms for load balancing on trees with finitely-divisible loads (token distribution). We present improved analysis of an existing protocol, and in particular, establish a logarithmic upper bound on the discrepancy of the final distribution. Our second contribution is a new algorithm, which assuming each node has knowledge of the total number of nodes, determines a perfectly balanced distribution.
7215582
Light edges in degree-constrained graphs
Let @a denote the average degree, and @d denote the minimum degree of a graph. An edge is light if both its endpoints have degree bounded by a constant depending only on @a and @d. A graph is degree-constrained if @a<2@d. The primary result of this paper is that every degree-constrained graph has a light edge. Most previous results in this direction have been for embedded graphs. This result is extended in a variety of ways. First it is proved that there exists a constant c(@a,@d) such that for every 0=<@e
14221100
Graph Treewidth and Geometric Thickness Parameters
Consider a drawing of a graph G in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of G, is the classical graph parameter thicknessθ(G). By restricting the edges to be straight, we obtain the geometric thickness${\bar\theta}$(G). By further restricting the vertices to be in convex position, we obtain the book thicknessbt(G). This paper studies the relationship between these parameters and the treewidth of G. Let $\theta({\mathcal T}_{k}) / {\bar\theta}({\mathcal T}_{k}) / {\tt bt}({\mathcal T}_{k})$denote the maximum thickness / geometric thickness / book thickness of a graph with treewidth at most k. We prove that: 
 
– $\theta({\mathcal T}_{k})={\bar\theta}({\mathcal T}_{k}) = \lceil k/2 \rceil$, and 
 
– ${\tt bt}({\mathcal T}_{k}) = k$for k≤2, and ${\tt bt}({\mathcal T}_{k}) = k+1$for k≥3. 
 
The first result says that the lower bound for thickness can be matched by an upper bound, even in the more restrictive geometric setting. The second result disproves the conjecture of Ganley and Heath [Discrete Appl. Math. 2001] that ${\tt bt}({\mathcal T}_{k}) = k$for all k. Analogous results are proved for outerthickness, arboricity, and star-arboricity.
5462033
Accuracy vs. performance in parallel simulation of interconnection networks
Parallel simulation is emerging as the dominant technique for studying parallel computers. However the interconnection networks of these machines can be modeled at many different levels of abstraction, allowing researchers to trade off accuracy and performance. We use the Wisconsin Wind Tunnel, a parallel simulator for cache-coherent shared-memory machines, to study the trade-offs of accuracy versus performance for six different network simulation models. We evaluate these models for a variety of parallel applications, cache-coherence protocols, and topologies. We show that only the two most expensive models-which model contention at individual links-are robust in the presence of high network loads or non-uniform traffic patterns.<<ETX>>
2320430
SafetyNet: improving the availability of shared memory multiprocessors with global checkpoint/recovery
We develop an availability solution, called SafetyNet, that uses a unified, lightweight checkpoint/recovery mechanism to support multiple long-latency fault detection schemes. At an abstract level, SafetyNet logically maintains multiple, globally consistent checkpoints of the state of a shared memory multiprocessor (i.e., processors, memory, and coherence permissions), and it recovers to a pre-fault checkpoint of the system and re-executes if a fault is detected. SafetyNet efficiently coordinates checkpoints across the system in logical time and uses "logically atomic" coherence transactions to free checkpoints of transient coherence state. SafetyNet minimizes performance overhead by pipelining checkpoint validation with subsequent parallel execution.We illustrate SafetyNet avoiding system crashes due to either dropped coherence messages or the loss of an interconnection network switch (and its buffered messages). Using full-system simulation of a 16-way multiprocessor running commercial workloads, we find that SafetyNet (a) adds statistically insignificant runtime overhead in the common-case of fault-free execution, and (b) avoids a crash when tolerated faults occur.