Search

Set agreement and renaming are two tasks that allow processes to coordinate, even when agreement is impossible. In k -set agreement , n processes must decide on at most k of their input values. While n -set agreement is trivially wait-free solvable by each process deciding on its input, ( n − 1 ) -set agreement is not wait-free solvable. In M -renaming , processes must decide on distinct names in a range of size M . For any number n of processes, ( 2 n − 1 ) -renaming is wait-free solvable, but surprisingly, ( 2 n − 2 ) -renaming is wait-free solvable if and only if n is not a prime power; the only previous lower bound on the number of names necessary for renaming, when n is not a prime power, is n + 1 . In adaptive renaming, M decreases when the number p of participants in the execution decreases. It is known that ( 2 p − 1 ) -adaptive renaming is wait-free solvable, while ( 2 p − ⌈ p n − 1 ⌉ ) -adaptive renaming is not. This paper presents counting-based proofs for the above mentioned impossibility results: n processes can wait-free solve neither ( n − 1 ) -set agreement nor ( 2 p − ⌈ p n − 1 ⌉ ) -adaptive renaming; if n is a prime power, n processes cannot wait-free solve ( 2 n − 2 ) -renaming. For an arbitrary number of processes, we give a lower bound for renaming, by reduction from renaming for a different number of processes, and relying on the distribution of prime numbers. Our proofs combine simple operational properties of a restricted set of executions with elementary counting arguments to show the existence of an execution violating the task’s conditions. This makes the proofs easier to understand, verify, and, we hope, extend. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the complexity of deciding determinism of unary languages. First, we give a method to derive a set of arithmetic progressions from a regular expression E over a unary alphabet, and establish relations between numbers represented by these arithmetic progressions and words in L ( E ) . Next, we define a problem relating to arithmetic progressions and investigate the complexity of this problem. Then by a reduction from this problem we show that deciding determinism of unary languages is coNP -complete. Finally, we extend our derivation method to expressions with counting, and prove that deciding whether an expression over a unary alphabet with counting defines a deterministic language is in Π 2 p . We also establish a tight upper bound for the size of the minimal DFA for expressions with counting. [ABSTRACT FROM AUTHOR]

Abstract: Consider a graph and, for each vertex , a subset of neighbors of . A -coloring is a coloring of the elements of so that vertices appearing together in some receive pairwise distinct colors. An obvious lower bound for the minimum number of colors in such a coloring is the maximum size of a set , denoted by . In this paper we study graph classes for which there is a function , such that for any graph and any , there is a -coloring using at most colors. It is proved that if such a function exists for a class , then can be taken to be a linear function. It is also shown that such classes are precisely the classes having bounded star chromatic number. We also investigate the list version and the clique version of this problem, and relate the existence of functions bounding those parameters to the recently introduced concepts of classes of bounded expansion and nowhere-dense classes. [Copyright &y& Elsevier]

Abstract: A dominating set of graph is called metric-locating–dominating if it is also locating, that is, if every vertex is uniquely determined by its vector of distances to the vertices in . If moreover, every vertex not in is also uniquely determined by the set of neighbors of belonging to , then it is said to be locating–dominating. Locating, metric-locating–dominating and locating–dominating sets of minimum cardinality are called -codes, -codes and -codes, respectively. A Nordhaus–Gaddum bound is a tight lower or upper bound on the sum or product of a parameter of a graph and its complement . In this paper, we present some Nordhaus–Gaddum bounds for the location number , the metric-location–domination number and the location–domination number . Moreover, in each case, the graph family attaining the corresponding bound is fully characterized. [Copyright &y& Elsevier]

Abstract: This article concerns nonconvolutional type operators (also known as Journéʼs type operators) associated with a multiparameter family of dilations given by where and . We are especially interested in the boundedness of such operators on the multiparameter Hardy spaces. This work is motivated by Pipherʼs result on the boundedness of these operators from the multiparameter spaces to spaces for , and Journéʼs counter-example which shows that the number of parameter plays a crucial role in boundedness of singular integral operators on multiparameter Hardy spaces. Journéʼs work shows that there is a sharp difference between the situations for two and three or more parameters. We establish in this paper the necessary and sufficient conditions under which the singular integral operators in Journéʼs class are bounded on multiparameter spaces () with arbitrary number of parameters. [Copyright &y& Elsevier]