Coincidental extension of scattered context languages

All the results given in the paper hold true. In the proof of Theorem 1, change steps IV, V, and VI to IV. for every , add to P; V. for every , add , , , , , to P; VI. for every , add to P.     

Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines

This paper investigates two preemptive semi-online scheduling problems to minimize makespan on two uniform machines. In the first semi-online problem, we know in advance that all jobs have their processing times in between p and rp . In the second semi-online problem, we know the size of the largest job in advance. We design an optimal semi-online algorithm which is optimal for every combination of machine speed ratio and job processing time ratio for the first problem, and an optimal semi-online algorithm for every machine speed ratio for the second problem.Received: 2 December 2003, Published online: 16 January 2004This research is supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China, and National Natural Science Foundation of China (10271110).     

Element distinctness on one-tape Turing machines: a complete solution

We give a complete characterization of the complexity of the element distinctness problem for n elements of bits each on deterministic and nondeterministic one-tape Turing machines. We present an algorithm running in time for deterministic machines and nondeterministic solutions that are of time complexity . For elements of logarithmic size , on nondeterministic machines, these results close the gap between the known lower bound and the previous upper bound . Additional lower bounds are given to show that the upper bounds are optimal for all other possible relations between m and n. The upper bounds employ hashing techniques, while the lower bounds make use of the communication complexity of set disjointness.Received: 23 April 2001, Published online: 2 September 2003Holger Petersen: Supported by Deutsche Akademie der Naturforscher Leopoldina, grant number BMBF-LPD 9901/8-1 of Bundesministerium für Bildung und Forschung.     

Lower bounds for sense of direction in regular graphs

A graph G with n vertices and maximum degree cannot be given weak sense of direction using less than colours. It is known that n colours are always sufficient, and it was conjectured that just are really needed, that is, one more colour is sufficient. Nonetheless, it has been shown [3] that for sufficiently large n there are graphs requiring more colours than . In this paper, using recent results in asymptotic graph enumeration, we show that (surprisingly) the same bound holds for regular graphs. We also show that colours are necessary, where d _G is the degree of G.Received: April 2002, Accepted: April 2003, Sebastiano Vigna: Partially supported by the Italian MURST (Finanziamento di iniziative di ricerca diffusa condotte da parte di giovani ricercatori).The results of this paper appeared in a preliminary form in Distributed Computing. 14th International Conference, DISC 2000, Springer-Verlag, 2000.     

Fast allocation and deallocation with an improved buddy system

We propose several modifications to the binary buddy system for managing dynamic allocation of memory blocks whose sizes are powers of two. The standard buddy system allocates and deallocates blocks in time in the worst case (and on an amortized basis), where n is the size of the memory. We present three schemes that improve the running time to O(1) time, where the time bound for deallocation is amortized for the first two schemes. The first scheme uses just one more word of memory than the standard buddy system, but may result in greater fragmentation than necessary. The second and third schemes have essentially the same fragmentation as the standard buddy system, and use bits of auxiliary storage, which is but for all and . Finally, we present simulation results estimating the effect of the excess fragmentation in the first scheme.Received: 4 May 2003, Published online: 22 December 2004Gerth Stølting Brodal: Supported by the Carlsberg Foundation (contract number ANS-0257/20). Partially supported by the Future and Emerging Technologies Programme of the EU under contract number IST-1999-14186 (ALCOM-FT). Basic Research in Computer Science, www.brics.dk, funded by the Danish National Research Foundation.Erik D. Demaine: Partially supported by the Natural Science and Engineering Research Council of Canada (NSERC).J. Ian Munro: Supported by the Natural Science and Engineering Research Council of Canada (NSERC) and the Canada Research Chair in Algorithm Design.This paper includes several results that appeared in preliminary form in the Proceedings of the 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FST & TCS99) [8].     

Condition-based consensus solvability: a hierarchy of conditions and efficient protocols

The condition-based approach for consensus solvability consists of identifying sets of input vectors, called conditions, for which there exists an asynchronous protocol solving consensus despite the occurrence of up to f process crashes. This paper investigates , the largest set of conditions which allow us to solve the consensus problem in an asynchronous shared memory system.The first part of the paper shows that is made up of a hierarchy of classes of conditions, where d is a parameter (called degree of the condition), starting with and ending with d = 0, where . We prove that each one is strictly contained in the previous one: . Various properties of the hierarchy are also derived. It is shown that a class can be characterized in two equivalent but complementary ways: one is convenient for designing protocols while the other is for analyzing the class properties. The paper also defines a linear family of conditions that can be used to derive many specific conditions. In particular, for each d, two natural conditions are presented.The second part of the paper is devoted to the design of efficient condition-based protocols. A generic condition-based protocol is presented. This protocol can be instantiated with any condition C, , and requires at most shared memory read/write operations per process in the synchronization part of the protocol. Thus, the value (f-d) represents the difficulty of the class . An improvement of the protocol for the conditions in is also presented.Received: 15 November 2001, Accepted: 15 April 2003, Published online: 6 February 2004Parts of it have previously appeared in [23] and [25].     

Cardinal interpolation with periodic polysplines on strips

Abstract  We obtain a multivariate extension of a classical result of Schoenberg on cardinal spline interpolation. Specifically, we prove the existence of a unique function in , polyharmonic of order p on each strip , , and periodic in its last n variables, whose restriction to the parallel hyperplanes , , coincides with a prescribed sequence of n-variate periodic data functions satisfying a growth condition in . The constructive proof is based on separation of variables and on Micchelli’s theory of univariate cardinal -splines. Keywords: cardinal -splines, polyharmonic functions, multivariable interpolation Mathematics Subject Classification (2000): 41A05, 41A15, 41A63     

Self-embedded context-free grammars with regular counterparts

In general, it is undecidable if an arbitrary context-free grammar has a regular solution. Past work has focused on special cases, such as one-letter grammars, non self-embedded grammars and the finite-language grammars, for which regular counterparts have been proven to exist. However, little is known about grammars with the self-embedded property. Using systems of equations, we highlight a number of subclasses of grammars, with self-embeddedness terms, such as and , that can still have regular languages as solutions. Constructive proofs that allow these subclasses of context-free grammars to be transformed to regular expressions are provided. We also point out a subclass of context-free grammars that is inherently non-regular. Our latest results can help demarcate more precisely the known boundaries between the regular and non-regular languages, within the context-free domain.Received: 17 January 2003, Published online: 17 February 2004Stefan Andrei: stefan@infoiasi.ro     

Constant-time distributed dominating set approximation

Finding a small dominating set is one of the most fundamental problems of classical graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary, possibly constant parameter k and maximum node degree , our algorithm computes a dominating set of expected size in rounds. Each node has to send messages of size . This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds.Received: 9 September 2003, Accepted: 2 September 2004, Published online: 13 January 2005The work presented in this paper was supported (in part) by the National Competence Center in Research on Mobile Information and Communication Systems (NCCR-MICS), a center supported by the Swiss National Science Foundation under grant number 5005-67322.     

Matching of graphical symbols in line-drawing images using angular signature information

In this paper, a method for matching complex objects in line-drawings is presented. Our approach is based on the notion of -signatures, which are a special kind of histogram of forces [17,19,28]. Such histograms have low time complexity and describe signatures that are invariant to fundamental geometrical transformations such as scaling, translation, symmetry, and rotation. This article presents a new application of this notion in the field of symbol identification and recognition. To improve the efficiency of matching, we propose using an approximation of the -signature from Fourier series and the associated matching.Received: 7 October 2002, Accepted: 1 December 2002, Published online: 4 July 2003     

The complexity of constructing pseudorandom generators from hard functions

We study the complexity of constructing pseudorandom generators (PRGs) from hard functions, focussing on constant-depth circuits. We show that, starting from a function computable in alternating time O(l) with O(1) alternations that is hard on average (i.e. there is a constant such that every circuit of size fails to compute f on at least a 1/poly(l) fraction of inputs) we can construct a computable by DLOGTIME-uniform constant-depth circuits of size polynomial in n. Such a PRG implies under DLOGTIME-uniformity. On the negative side, we prove that starting from a worst-case hard function (i.e. there is a constant such that every circuit of size fails to compute f on some input) for every positive constant there is no black-box construction of a computable by constant-depth circuits of size polynomial in n. We also study worst-case hardness amplification, which is the related problem of producing an average-case hard function starting from a worst-case hard one. In particular, we deduce that there is no blackbox worst-case hardness amplification within the polynomial time hierarchy. These negative results are obtained by showing that polynomialsize constant-depth circuits cannot compute good extractors and listdecodable codes.     

A comparison of pebble tree transducers with macro tree transducers

The n-pebble tree transducer was recently proposed as a model for XML query languages. The four main results on deterministic transducers are: First, (1) the translation of an n-pebble tree transducer can be realized by a composition of n+1 0-pebble tree transducers. Next, the pebble tree transducer is compared with the macro tree transducer, a well-known model for syntax-directed semantics, with decidable type checking. The -pebble tree transducer can be simulated by the macro tree transducer, which, by the first result, implies that (2) can be realized by an (n+1)-fold composition of macro tree transducers. Conversely, every macro tree transducer can be simulated by a composition of 0-pebble tree transducers. Together these simulations prove that (3) the composition closure of n-pebble tree transducers equals that of macro tree transducers (and that of 0-pebble tree transducers). Similar results hold in the nondeterministic case. Finally, (4) the output languages of deterministic n-pebble tree transducers form a hierarchy with respect to the number n of pebbles.This revised version was published online in September 2003 with corrections to type sizes.Received: 16 January 2003, Sebastian Maneth: Present address: Swiss Institute of Technology Lausanne, Programming Methods Laboratory (LAMP), 1015 Lausanne, Switzerland, e-mail (sebastian.maneth@epfl.ch)     

Convex Drawings of 3-Connected Plane Graphs

We use Schnyder woods of 3-connected planar graphs to produce convex straight-line drawings on a grid of size The parameter depends on the Schnyder wood used for the drawing. This parameter is in the range The algorithm is a refinement of the face-counting algorithm; thus, in particular, the size of the grid is at most The above bound on the grid size simultaneously matches or improves all previously known bounds for convex drawings, in particular Schnyder's and the recent Zhang and He bound for triangulations and the Chrobak and Kant bound for 3-connected planar graphs. The algorithm takes linear time. The drawing algorithm has been implemented and tested. The expected grid size for the drawing of a random triangulation is close to For a random 3-connected plane graph, tests show that the expected size of the drawing is      

Safety assurance via on-line monitoring

This paper proposes a new approach and new techniques for on-line monitoring of concurrent programs to ensure that some of their safety properties are not violated. The techniques modify erroneous systems, which violate a certain safety property, into new systems which satisfy the safety property. It does so by adding a new layer that controls the scheduling of steps in the system. We formally characterize the relationship between the erroneous and the new system. Safety monitors for mutual-exclusion, -exclusion, and the producer-consumer tasks are presented. Proofs for the mutual-exclusion task and the -exclusion task are presented to demonstrate the applicability of our approach.Received: May 2001, Accepted: December 2002, An extended abstract of this work appears in the Proceedings of the fifth International Symposium on Autonomous Decentralized Systems (ISADS) 2001. Part of this work was done while the first author visited Wayne State University.     

Complexity of some arithmetic problems for binary polynomials

We study various combinatorial complexity measures of Boolean functions related to some natural arithmetic problems about binary polynomials, that is, polynomials over . In particular, we consider the Boolean function deciding whether a given polynomial over is squarefree. We obtain an exponential lower bound on the size of a decision tree for this function, and derive an asymptotic formula, having a linear main term, for its average sensitivity. This allows us to estimate other complexity characteristics such as the formula size, the average decision tree depth and the degrees of exact and approximative polynomial representations of this function. Finally, using a different method, we show that testing squarefreeness and irreducibility of polynomials over cannot be done in for any odd prime p. Similar results are obtained for deciding coprimality of two polynomials over as well.     

A note on pure and <Emphasis Type="Italic">p</Emphasis>-pure languages

A variation of first order logic with variables for exponents is developed to solve some problems in the setting of rational languages on the free monoid, implying in particular algorithms for purity and p-purity. This same problem is addressed for the case of rational free group languages, and characterizations of the rational subsets of involved are also obtained.Received: 5 December 2002, Pedro V. Silva: http://www.fc.up.pt/cmup     

Efficient Algorithms for k Maximum Sums

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers and an integer parameter k, the problem involves finding the k largest values of for The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a -time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in time in the worst case. Our algorithm is optimal for and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well.     

Eye and gaze tracking for interactive graphic display

This paper describes a computer vision system based on active IR illumination for real-time gaze tracking for interactive graphic display. Unlike most of the existing gaze tracking techniques, which often require assuming a static head to work well and require a cumbersome calibration process for each person, our gaze tracker can perform robust and accurate gaze estimation without calibration and under rather significant head movement. This is made possible by a new gaze calibration procedure that identifies the mapping from pupil parameters to screen coordinates using generalized regression neural networks (GRNNs). With GRNNs, the mapping does not have to be an analytical function and head movement is explicitly accounted for by the gaze mapping function. Furthermore, the mapping function can generalize to other individuals not used in the training. To further improve the gaze estimation accuracy, we employ a hierarchical classification scheme that deals with the classes that tend to be misclassified. This leads to a improvement in classification error. The angular gaze accuracy is about horizontally and vertically. The effectiveness of our gaze tracker is demonstrated by experiments that involve gaze-contingent interactive graphic display.Received: 21 July 2002, Accepted: 3 February 2004, Published online: 8 June 2004 Correspondence to: Qiang Ji     

An Application of an Initialization Protocol to Permutation Routing in a Single-Hop Mobile Ad Hoc Networks

In 1999 Nakano, Olariu, and Schwing in [20], they showed that the permutation routing of n items pretitled on a mobile ad hoc network (MANET for short) of p stations (p known) and k channels (MANET{(n, p, k)) with k < p, can be carried out in broadcast rounds if k p and if each station has a -memory locations. And if k and if each station has a -memory locations, the permutations of these n pretitled items can be done also in broadcast rounds. They used two assumptions: first they suppose that each station of the mobile ad hoc network has an identifier beforehand. Secondly, the stations are partitioned into k groups such that each group has stations, but it was not shown how this partition can be obtained. In this paper, the stations have not identifiers beforehand and p is unknown. We develop a protocol which first names the stations, secondly gives the value of p, and partitions stations in groups of stations. Finally we show that the permutation routing problem can be solved on it in broadcast rounds in the worst case. It can be solved in broadcast rounds in the better case. Note that our approach does not impose any restriction on k.     

The Expected Size of the Rule k Dominating Set

Dai, Li, and Wu proposed Rule k, a localized approximation algorithm that attempts to find a small connected dominating set in a graph. In this paper we consider the "average-case" performance of two closely related versions of Rule k for the model of random unit disk graphs constructed from n random points in an square. We show that if and then for both versions of Rule k, the expected size of the Rule k dominating set is as It follows that, for in a suitable range, the expected size of the Rule k dominating sets are within a constant factor of the optimum.