Showing 1 to 10 of 1605 matching Articles
Results per page:
Export (CSV)
By
Rozenberg, G.; Lindenmayer, A.
43 Citations
Summary
A locally catenative sequence of strings of letters is such that each string in the sequence, after an initial stretch, is formed by concatenating strings which occurred at some specified distances previously in the sequence. These kinds of structures are frequently encountered in biological development, particularly in the case of compound branching structures or compound leaves. Developmental systems have been formally defined in previous publications. One of the present results is that dependent PDOL systems can produce sequences for every locally catenative formula (PDOL systems are propagating, deterministic developmental systems without interactions). Every dependent PDOL system produces a sequence which satisfies an infinite class of locally catenative formulas. Some of these formulas can be derived from a minimum formula, but a sequence may satisfy more than one minimum formulas.
more …
By
Karr, Michael
206 Citations
Summary
Several optimizations of programs can be performed when in certain regions of a program equality relationships hold between a linear combination of the variables of the program and a constant. This paper presents a practical approach to detecting these relationships by considering the problem from the viewpoint of linear algebra. Key to the practicality of this approach is an algorithm for the calculation of the “sum” of linear subspaces.
more …
By
Taubner, Dirk; Vogler, Walter
8 Citations
Summary
The (linear) failures semantics is a wellknown model for the theoretical version of Hoare's CSP. We generalize this semantics by taking steps (i.e. multisets of simultaneously occurring actions) instead of single actions as the basic execution unit. Hence opposed to the linear semantics — where parallelism is modelled as arbitrary interleaving in order to avoid technical complication — the step failures semantics models parallelism explicitly and is equally easy to manage. In particular a sound and complete proof system is given. Opposed to the linear model divergence is treated uniformly here. The relation to the linear semantics can be established using our newly introduced deparallelize operator.
more …
By
Levcopoulos, Christos; Overmars, Mark H.
36 Citations
Summary
In this paper a new data structure is described for performing member and neighbor queries in O(logn) time that allows for O(1) worstcase update time once the position of the inserted or deleted element is known. In this way previous solutions that achieved only O(1) amortized time or O(log^{*}n) worstcase time are improved. The method is based on a combinatorial result on the height of piles that are split after some fixed number of insertions. This combinatorial result is interesting in its own right and might have other applications as well.
more …
By
Engelfriet, Joost
Treewalking tree transducers can be typechecked in double exponential time. More generally, compositions of k treewalking tree transducers can be typechecked in (k + 1)fold exponential time. Consequently kpebble tree transducers, which form a model of XML transformations and XML queries, can be typechecked in (k + 2)fold exponential time. The results hold for both ranked and unranked trees.
more …
By
Wand, Mitchell
17 Citations
Summary
Inverting the adage that a data type is just a simple programming language, we take the position that a programming language is, semantically, just a complex data type; evaluation of a program is just another operation in the data type. The algebraic approach to data types may then be applied. We make a distinction between specification and modelling, and we emphasize the use of firstorder identities as a specification language rather than as a tool for modelbuilding. Denotational and operational semantics are discussed. Techniques are introduced for proving the equivalence of specifications. Reynolds' lambdacalculus interpreter is analyzed as an example.
more …
By
Björklund, Henrik; Martens, Wim; Schwentick, Thomas
We study the containment, satisfiability, and validity problems for conjunctive queries over trees with respect to a schema. We show that conjunctive query containment and validity are 2EXPTIME complete with respect to a schema, in both cases where the schema is given as a DTD or as a tree automaton. Furthermore, we show that satisfiability for conjunctive queries with respect to a schema can be decided in NP . The problem is NP hard already for queries using only one kind of axis. Finally, we consider conjunctive queries that can test for equalities and inequalities of data values. Here, satisfiability and validity are decidable, but containment is undecidable, even without schema information. On the other hand, containment with respect to a schema becomes decidable again if the “larger” query is not allowed to use both equalities and inequalities.
more …
By
Shore, John E.
47 Citations
Summary
This paper presents new results concerning the use of information theoretic inference techniques in system modeling and concerning the widespread applicability of certain simple queuing theory formulas. For the case when an M/G/1 queue provides a reasonable system model but when information about the service time probability density is limited to knowledge of a few moments, entropy maximization and crossentropy minimization are used to derive information theoretic approximations for various performance distributions such as queue length, waiting time, residence time, busy period, etc. Some of these approximations are shown to reduce to exact M/M/1 results when G = M. For the case when a G/G/1 queue provides a reasonable system model, but when information about the arrival and service distributions is limited to the average arrival and service rates, it is shown that various well known M/M/1 formulas are information theoretic approximations. These results not only provide a new method for approximating the performance distributions, but they help to explain the widespread applicability of the M/M/1 formulas.
more …
By
Fachini, E.; Monti, A.; Napoli, M.; Parente, D.
Show all (4)
2 Citations
In this paper closure properties and decision problems for families of languages accepted by deterministic and nondeterministic systolic binary Ytree automata are studied. Non closure results under basic language operations are stated by means of new nonacceptability criteria for these classes of automata. Necessary and sufficient conditions are given in terms of the shape of the underlying Ytree, for the closure under λfree regular substitution, concatenation, inverse homomorfism and for the closure under right concatenation with and quotient by finite sets. Moreover in the nondeterministic case necessary and sufficient conditions are given again in terms of the shape of the underlying Ytree for the closure under right concatenation with regular sets and for the decidability of the problems of emptiness, finiteness, equivalence and coemptiness. A sufficient condition is given for the decidability of the stability problem, in the deterministic case, while some undecidability results are proved in the nondeterministic case.
more …
By
Ţiplea, Ferucio Laurenţiu; Enea, Constantin
2 Citations
The use of abstraction in the context of abstract data types, is investigated. Properties to be checked are formulas in a first order logic under Kleene's 3valued interpretation. Abstractions are defined as pairs consisting of a congruence and a predicate interpretation. Three types of abstractions are considered,∀∀, ∀∃ and ∃^{0,1}∀, and for each of them corresponding property preservation results are established. An abstraction refinement property is also obtained. It shows how one can pass from an existing abstraction to a (less) finer one. Finally, equationally specified abstractions in the context of equationally specified abstract data types are discussed and exemplified.
more …
