Consider the following kinds of sets: the set of all possible distances between two vertices of a directed graph;any set of integers that is either finite or periodic for all n greater or equal to some no (such a set ...
详细信息
Consider the following kinds of sets: the set of all possible distances between two vertices of a directed graph;any set of integers that is either finite or periodic for all n greater or equal to some no (such a set is called ultimately periodic);a context-free language over an alphabet with one letter (such a language is also regular);the set of all possible lengths of words of a context-free language. All these sets are isomorphic relatively to the operations of union (or sum), concatenation and Kleene (or transitive) closure. Furthermore, they all share a particularly important property which is not valid in some similar algebraic structure - the concatenation is commutative. The purpose of this paper is to investigate the representation and properties of these sets and also the algorithms to compute the operations mentioned above. The concepts of linear number and DELTA-sum are developed in order to provide convenient methods of representation and manipulation. It should be noted that although DELTA-sums and regular expressions (or finite automata) over a one-letter alphabet denote essentially the same sets, the corresponding algebras are quite different. For example, it is always possible to eliminate the closure and concatenation operations from a DELTA-sum by expanding it as a sum of linear numbers. No such elimination is possible for regular expressions (although special forms of regular expressions or finite automata are sufficient to denote regular sets over one-letter alphabets). The algorithms using DELTA-sums are often faster and simpler than those based on finite automata or regular expressions over a one-letter alphabet. We think that this improvement comes from the fact that a set of words over one letter is represented by the set of their lengths and manipulated by arithmetic operations. We apply these methods to the first kind of sets listed above and present new algorithms dealing with a variety of problems related to distances in directed graphs
Let T and R be two arbitrary ordered trees, \T\ greater-than-or-equal-to \R\, whose nodes are labelled over an alphabet A. We devise a simple solution for detecting all the common subtrees in O(\T\) time and space if ...
详细信息
Let T and R be two arbitrary ordered trees, \T\ greater-than-or-equal-to \R\, whose nodes are labelled over an alphabet A. We devise a simple solution for detecting all the common subtrees in O(\T\) time and space if the size of A is finite, and O(\T\ log min(\A\, \T\)) time otherwise. We solve the problem of finding in T and R all occurrences (if any) of any given tree B in either O(\T\/\B\) or O(\B\+\T\/\B\) time. This requires to set up a simple data structure in O(\T\) time that allows to find all maximal subtrees of B in O(\B\) time and to solve other related problems.
作者：
NERAUD, JLIR
LITP Institut Blaise Pascal Université de Rouen
Faculté des Sciences
Place Emile Blondel F-76134 Mont-Saint-Aignan France
Given a finite subset X of a free monoid A*, we define the rank of X as r(X) = min {Absolute value of Y: X subset-or-equal-to Y*}. The problem we study here is to decide whether or not r(X) less-than-or-equal-to 2. We...
详细信息
Given a finite subset X of a free monoid A*, we define the rank of X as r(X) = min {Absolute value of Y: X subset-or-equal-to Y*}. The problem we study here is to decide whether or not r(X) less-than-or-equal-to 2. We propose an O(n ln2 m) algorithm, where n stands for the sum of the lengths of the words in X, and m stands for the length of the longest word.
Cantor conceived set theory in a sequence of six papers published in theMathematische Annalen during the five year period 1879-1884. In the fifth of these papers, publishedin 1883, he stated as a law of thought (Denkg...
详细信息
Cantor conceived set theory in a sequence of six papers published in theMathematische Annalen during the five year period 1879-1884. In the fifth of these papers, publishedin 1883, he stated as a law of thought (Denkgesetz) that every set can be well-ordered or, moreprecisely, that it is always possible to bring any well-defined set into the form of a well-orderedset. Now to call it a law of thought was implicitly to claim self-evidence for it, but he must havegiven up that claim at some point, because in the 1890s he made an unsuccessful attempt atdemonstrating the well-ordering principle.
Simulation models are used to emulate real-world phenomena, and errors are inevitable in the numerical computation process. Owing to that, simulation models need to be verified and validated to ensure the models and t...
详细信息
Simulation models are used to emulate real-world phenomena, and errors are inevitable in the numerical computation process. Owing to that, simulation models need to be verified and validated to ensure the models and their implementations are correct. In this paper, V&V has been done for the micro3d discrete dislocation dynamics (DDD) model by comparing simulation results with corresponding theory, including any analytical solutions, other numerical solutions and experimental data. DDD simulations are a powerful simulation methodology that can help researchers better understand the plastic behavior of crystalline materials. In this study, parametric analyses for DDD simulations parameters have been performed. In addition, simulation results are verified and validated.
We consider decision problems that are solved in a distributed fashion by synchronous mobile agents operating in an unknown, anonymous network. Each agent has a unique identifier and an input string and they have to d...
详细信息
We consider decision problems that are solved in a distributed fashion by synchronous mobile agents operating in an unknown, anonymous network. Each agent has a unique identifier and an input string and they have to decide collectively a property which may involve their input strings, the graph on which they are operating, and their particular starting positions. Building on recent work by Fraigniaud and Pelc [J. Parallel Distrib. Comput, vol. 109, pp. 117-128], we introduce several natural new computability classes allowing for a finer classification of problems below MAV or its complement class co-MAV, the former being the class of problems that are verifiable when the agents are provided with an appropriate certificate. We provide inclusion and separation results among all these classes. We also determine their closure properties with respect to set-theoretic operations. Our main technical tool, which is of independent interest, is a new metaprotocol that enables the execution of a possibly infinite number of mobile agent protocols essentially in parallel, similarly to the well-known dovetailing technique from classical computability theory. (C) 2018 Elsevier Inc. All rights reserved.
A strong body of opinion has recently favoured the buckled dimer type of model for the Si{100} surface and we compare LEED calculations for two such models with experiment. The first model is that of Yin and Cohen whi...
详细信息
A strong body of opinion has recently favoured the buckled dimer type of model for the Si{100} surface and we compare LEED calculations for two such models with experiment. The first model is that of Yin and Cohen which was proposed on the basis of minimization of the Hellman-Feynman forces using a self-consistent, local density, pseudopotential theory. The second model is that of Yang, Jona and Marcus which was found by varying structural parameters to obtain agreement with the LEED data. For comparison we also include the symmetric dimer model of Tong and Maldonado. Our calculations are fully dynamical and we treat the actual structures proposed without imposing any limitations to aid computation. We present visual comparisons of calculations and experimental data and also calculate the Pendry R factors. We find that the Yang, Jona and Marcus model is in best agreement with experiment, but the improvement over the other two models does not seem to be as great as one might expect if the structure were essentially correct. There is still some question therefore as to whether the model needs only minor modifications or significant changes.
The Annual Boole Lecture was established and is sponsored by the Boole Centre for Research in Informatics, the Cork Constraint computation Centre, the Department of Computer Science, and the School of Mathematics, App...
详细信息
The Annual Boole Lecture was established and is sponsored by the Boole Centre for Research in Informatics, the Cork Constraint computation Centre, the Department of Computer Science, and the School of Mathematics, Applied Mathematics and Statistics, at University College Cork. The series in named in honour of George Boole, the first professor of Mathematics at UCC, whose seminal work on logic in the mid-1800s is central to modern digital computing. To mark this great contribution, leaders in the field of computing and mathematics are invited to talk to the general public on directions in science, on past achievements and on visions for the future.
A physical system that retrieves information from the past and acts on it appropriately can efficiently solve difficult combinatorial-optimization problems.
A physical system that retrieves information from the past and acts on it appropriately can efficiently solve difficult combinatorial-optimization problems.
暂无评论