The Knuth-Bendix completion algorithm is a procedure which generates confluent and terminating sets of rewrite rules. The algorithm has many applications: the resulting rules can be used as a decision procedure for eq...
详细信息
The Knuth-Bendix completion algorithm is a procedure which generates confluent and terminating sets of rewrite rules. The algorithm has many applications: the resulting rules can be used as a decision procedure for equality or, in the case of program synthesis, as a program. We present an effective algorithm to solve some cases of divergence in the Knuth-Bendix completion algorithm, starting from a grammar characterising the infinite rule set. We replace an infinite set of rewrite rules by a finite complete set by enriching the original (order-sorted) signature with new sorts and new operator arities, while remaining within a conservative extension of the original system and within the original term set. The complexity of the new rewriting system is no worse than that of the original system. We characterise the class of examples for which this approach is applicable and give some sufficient conditions for the algorithm to succeed.
The results of a volunteer engagement characterization study in two astronomy projects (Galaxy Zoo and the Milky Way Project) found a diversity of engagement patterns in terms of frequency, daily productivity, duratio...
详细信息
The results of a volunteer engagement characterization study in two astronomy projects (Galaxy Zoo and the Milky Way Project) found a diversity of engagement patterns in terms of frequency, daily productivity, duration of typical contribution session, and the amount of time devoted to the project.
Recall that a semigroup has the property P-n* if for any sequence of n of its elements, two differently permuted products of these n elements are equal. Let s be an infinite Sturmian word (on a 2-letter alphabet A). W...
详细信息
Recall that a semigroup has the property P-n* if for any sequence of n of its elements, two differently permuted products of these n elements are equal. Let s be an infinite Sturmian word (on a 2-letter alphabet A). We prove that the Rees quotient of A* by the set of the non-factors of s has P-4* and that this result is the best possible. We prove also that if St is the set of all finite Sturmian words, then the Rees quotient A*/(A* - St) has P-8*.
In this paper, we are concerned with finite p-s-composed codes, that is with codes obtained by composition of finite prefix and suffix codes. We give a method to decompose a finite prefix-suffix composed code in a min...
详细信息
In this paper, we are concerned with finite p-s-composed codes, that is with codes obtained by composition of finite prefix and suffix codes. We give a method to decompose a finite prefix-suffix composed code in a minimal number of prefix and suffix codes. Using this method, we establish that every prefix-suffix composed n-word code (n greater than or equal to 3) can be expressed as the composition of at most 2n - 3 prefix and suffix codes. We show that for all n, this limit is reached, that is, there exists a ps-composed n-word code that cannot be expressed as the composition of less than 2n - 3 prefix and suffix codes. Then we give an example of a three-word code which is not prefix-suffix composed, refuting a conjecture proposed by Restive et al. in 1989.
Founded by J.F. Ritt, Differential Algebra is a true part of Algebra so that constructive and algorithmic problems and methods appear in this field. In this talk, I do nor intend to give an exhaustive survey of algori...
详细信息
Founded by J.F. Ritt, Differential Algebra is a true part of Algebra so that constructive and algorithmic problems and methods appear in this field. In this talk, I do nor intend to give an exhaustive survey of algorithmic aspects of Differential Algebra but I only propose some examples to give an insight of the stare of knowledge in this domain. Some problems are known to have an effective solution, others have an efficient effective solution which is implemented in recent computer algebra systems, and the decidability of some others is still an open question, which does not prevent computations from leading to interesting results. Liouville's theory of integration in finite terms and Risch's theorem are examples of problems that computer algebra systems now deal with very efficiently (implementation work by M. Bronstein). In what concerns Linear differential equations of arbitrary order, a basis for the vector space of all liouvillian solutions can ''in principle'' be computed effectively thanks to a theorem of Singer's [17, 22];the complexity bound is actually awful and a lot of work is done or in progress, especially by M. Singer and F, Ulmer, to give realistic algorithms [20, 21] for third-order linear differential equations. Existence of liouvillian first integrals is a way to make precise the notion of integrability of vector fields. Even in the simplest case of three-dimensional polynomial vector fields, no decision procedure is known for this existence. Nevertheless, explicit computations with computer algebra yield interesting solutions for special examples. In this case, the process of looking for so-called Darboux curves can only be called a method but not an algorithm;for a given degree, this search is a classical algebraic elimination process but no bound is known on the degree of the candidate polynomials. This paper insists on the search of liouvillian first integrals of polynomial vector fields and a new result is given: the generic absence of such
Parallel and distributed derivations are introduced and studied in the single-pushout approach, which models rewriting by pushout constructions in appropriate categories of partial morphisms. We present a categorical ...
详细信息
Parallel and distributed derivations are introduced and studied in the single-pushout approach, which models rewriting by pushout constructions in appropriate categories of partial morphisms. We present a categorical framework for this approach in an axiomatic way. Models of this categorical framework are among others: graphs, hypergraphs, relational structures, and algebraic specifications with suitable partial morphisms. Several new results concerning parallelism and distributed parallelism are presented which are even new in the example categories.
The aim of this paper is to obtain real bounds on the accumulated roundoff error due to the addition of positive independent random variables in floating-point arithmetic. By ''real bounds'', we mean a...
详细信息
The aim of this paper is to obtain real bounds on the accumulated roundoff error due to the addition of positive independent random variables in floating-point arithmetic. By ''real bounds'', we mean an interval I such that the error belongs to I with a high probability. We show that the real bounds for a rather high probability (0.99 and more) are much tighter than those obtained from the known ''strict'' estimates. The length of the real distribution interval grows as fast as n(3/2) where n is the number of addends, i.e. n(1/2) times slower than what could be expected from the strict estimates. The method is extended to the process of numerical integration. Experimental results are given.
This paper presents an overview of past and current research in computational modelling of micro- and nanofluidic systems with particular focus on recent advances in multiscale modelling. Different mesoscale and hybri...
详细信息
This paper presents an overview of past and current research in computational modelling of micro- and nanofluidic systems with particular focus on recent advances in multiscale modelling. Different mesoscale and hybrid molecular-continuum methods are presented. The contributions of these methods to a broad range of applications, as well as the physical and computational modelling challenges associated with the development of these methods, are also discussed.
A generalized model of rough sets called variable precision model (VP-model), aimed at modelling classification problems involving uncertain or imprecise information, is presented. The generalized model inherits all b...
详细信息
A generalized model of rough sets called variable precision model (VP-model), aimed at modelling classification problems involving uncertain or imprecise information, is presented. The generalized model inherits all basic mathematical properties of the original model introduced by Pawlak. The main concepts are introduced formally and illustrated with simple examples. The application of the model to analysis of knowledge representation systems is also discussed.
We characterize AVL trees that have, for their heights and weights, the maximum numbers of nodes whose subtrees differ in height by one (imbalanced nodes). We obtain the result from a characterization of brother trees...
详细信息
We characterize AVL trees that have, for their heights and weights, the maximum numbers of nodes whose subtrees differ in height by one (imbalanced nodes). We obtain the result from a characterization of brother trees with the maximum space costs for their heights and weights. The proof is based on a novel tree transformation that is of interest in its own right.
暂无评论