Search results for "Computation theory"
showing 10 items of 336 documents
Back to “Reasoning”
2016
Is rigor always strictly related to precision and accuracy? This is a fundamental question in the realm of Fuzzy Logic; the first instinct would be to answer in the positive, but the question is much more complex than it appears, as true rigor is obtained also by a careful examination of the context, and limiting to a mechanical transfer of techniques, procedures and conceptual attitudes from one domain to another, such as from the pure engineering feats or the ones of mathematical logic to the study of human reasoning, does not guarantee optimal results. Starting from this question, we discuss some implications of going back to the very concept of reasoning as it is used in natural languag…
Stochastic Scheduling of Production Orders Under Uncertainty
2017
This paper attempts to solve the problem of searching minimum production order completion time variants by means of stochastic logical structures with all cost curve descent points and corresponding minimum-cost schedules. The analysis presented in this paper considers scheduling of unique and small batch production, predominantly to order, which accounts for changing requirements of the customer, the complexity and long production process makespan including its technical preparation. Scheduling of production order was performed by means of GAN networks and employed the concept of soft relations. The cost/time relation analysis is based on two-node network models using the cost curve. A new…
A challenging family of automata for classical minimization algorithms
2010
In this paper a particular family of deterministic automata that was built to reach the worst case complexity of Hopcroft's state minimization algorithm is considered. This family is also challenging for the two other classical minimization algorithms: it achieves the worst case for Moore's algorithm, as a consequence of a result by Berstel et al., and is of at least quadratic complexity for Brzozowski's solution, which is our main contribution. It therefore constitutes an interesting family, which can be useful to measure the efficiency of implementations of well-known or new minimization algorithms.
Self-stabilizing Balls & Bins in Batches
2016
A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be distributed to n bins (servers). In a seminal work, [Azar et al.; JoC'99] proposed the sequential strategy Greedy[d] for n = m. When thrown, a ball queries the load of d random bins and is allocated to a least loaded of these. [Azar et al.; JoC'99] showed that d=2 yields an exponential improvement compared to d=1. [Berenbrink et al.; JoC'06] extended this to m ⇒ n, showing that the maximal load difference is independent of m for d=2 (in contrast…
Handling precedence constraints in scheduling problems by the sequence pair representation
2015
In this paper, we show that sequence pair (SP) representation, primarily applied to the rectangle packing problems appearing in the VLSI industry, can be a solution representation of precedence constrained scheduling. We present three interpretations of sequence pair, which differ in complexity of schedule evaluation and size of a corresponding solution space. For each interpretation we construct an incremental precedence constrained SP neighborhood evaluation algorithm, computing feasibility of each solution in the insert neighborhood in an amortized constant time per examined solution, and prove the connectivity property of the considered neighborhoods. To compare proposed interpretations…
Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier
2019
Abstract The vehicle-routing problem with private fleet and common carrier (VRPPC) extends the capacitated VRP by considering the option of outsourcing customers to subcontractors at a customer-dependent cost instead of serving them with the private fleet. The VRPPC has important applications in small package shipping and manufacturing, but despite its relevance, no exact solution approach has been introduced so far. We propose a branch-price-and-cut algorithm that is able to solve small to medium-sized instances and provides tight lower bounds for larger instances from the literature. In addition, we develop a large neighborhood search that shows a decent solution quality and competitive r…
Le cône diamant symplectique
2009
Resume Si n + est le facteur nilpotent d'une algebre semi-simple g , le cone diamant de g est la description combinatoire d'une base d'un n + module indecomposable naturel. Cette notion a ete introduite par N.J. Wildberger pour sl ( 3 ) , le cone diamant de sl ( n ) est decrit dans Arnal (2006) [2] , celui des algebres semi-simples de rang 2 dans Agrebaoui (2008) [1] . Dans cet article, nous generalisons ces constructions au cas des algebres de Lie sp ( 2 n ) . Les tableaux de Young semi-standards symplectiques ont ete definis par C. De Concini (1979) [4] , ils forment une base de l'algebre de forme de sp ( 2 n ) . Nous introduisons ici la notion de tableaux de Young quasi standards symplec…
Exhaustive generation for permutations avoiding (colored) regular sets of patterns
2019
Abstract Despite the fact that the field of pattern avoiding permutations has been skyrocketing over the last two decades, there are very few exhaustive generating algorithms for such classes of permutations. In this paper we introduce the notions of regular and colored regular set of forbidden patterns, which are particular cases of right-justified sets of forbidden patterns. We show the (colored) regularity of several sets of forbidden patterns (some of them involving variable length patterns) and we derive a general framework for the efficient generation of permutations avoiding them. The obtained generating algorithms are based on succession functions, a notion which is a byproduct of t…
Catalan and Schröder permutations sortable by two restricted stacks
2020
Abstract Pattern avoiding machines were introduced recently by Claesson, Cerbai and Ferrari as a particular case of the two-stacks in series sorting device. They consist of two restricted stacks in series, ruled by a right-greedy procedure and the stacks avoid some specified patterns. Some of the obtained results have been further generalized to Cayley permutations by Cerbai, specialized to particular patterns by Defant and Zheng, or considered in the context of functions over the symmetric group by Berlow. In this work we study pattern avoiding machines where the first stack avoids a pair of patterns of length 3 and investigate those pairs for which sortable permutations are counted by the…
SPACES OF SMALL METRIC COTYPE
2010
Naor and Mendel's metric cotype extends the notion of the Rademacher cotype of a Banach space to all metric spaces. Every Banach space has metric cotype at least 2. We show that any metric space that is bi-Lipschitz equivalent to an ultrametric space has infinimal metric cotype 1. We discuss the invariance of metric cotype inequalities under snowflaking mappings and Gromov-Hausdorff limits, and use these facts to establish a partial converse of the main result.