Topology on words

We investigate properties of topologies on sets of finite and infinite words over a finite alphabet. The guiding example is the topology generated by the prefix relation on the set of finite words, considered as a partial order. This partial order extends naturally to the set of infinite words; hence it generates a topology on the union of the sets of finite and infinite words. We consider several partial orders which have similar properties and identify general principles according to which the transition from finite to infinite words is natural. We provide a uniform topological framework for the set of finite and infinite words to handle limits in a general fashion.     

Fair allocation of utilities in multirate multicast networks: aframework for unifying diverse fairness objectives

We study fairness in a multicast network. We assume that different receivers of the same session can receive information at different rates. We study a fair allocation of utilities, where the utility of a bandwidth is an arbitrary function of the bandwidth. The utility function is not strictly increasing, nor continuous in general. We discuss fairness issues in this general context. Fair allocation of utilities can be modeled as a nonlinear optimization problem. However, nonlinear optimization techniques do not terminate in a finite number of iterations in general. We present an algorithm for computing a fair utility allocation. Using specific fairness properties, we show that this algorithm attains global convergence and yields a fair allocation in polynomial number of iterations     

Verifiable shuffles: a formal model and a Paillier-based three-round construction with provable security

A shuffle takes a list of ciphertexts and outputs a permuted list of re-encryptions of the input ciphertexts. Mix-nets, a popular method for anonymous routing, can be constructed from a sequence of shuffles and decryption. We propose a formal model for security of verifiable shuffles and a new verifiable shuffle system based on the Paillier encryption scheme, and prove its security in the proposed dmodel. The model is general and can be extended to provide provable security for verifiable shuffle decryption.This paper is the extended version of the paper [37] presented at ACNS ‘04.     

考虑倒垛因素的轧制计划编制方法

在给定粗轧制计划的基础上考虑钢坯库倒垛优化, 编制详细的轧制计划; 建立以最小化轧制计划内钢坯出 库总倒垛次数与轧制单元之间切换机架次数为目标的多目标整数规划模型; 针对模型特征, 设计一种基于钢坯匹配的单亲遗传算法. 通过基于实际生产数据的实验验证, 相对于传统的手工计算方法, 所提出的算法在优化倒垛次数和切换机架次数上平均提升20 %, 算法和模型是可行且有效的.     

Regular Model Checking Using Inference of Regular Languages

Regular model checking is a method for verifying infinite-state systems based on coding their configurations as words over a finite alphabet, sets of configurations as finite automata, and transitions as finite transducers. We introduce a new general approach to regular model checking based on inference of regular languages. The method builds upon the observation that for infinite-state systems whose behaviour can be modelled using length-preserving transducers, there is a finite computation for obtaining all reachable configurations up to a certain length n. These configurations are a (positive) sample of the reachable configurations of the given system, whereas all other words up to length n are a negative sample. Then, methods of inference of regular languages can be used to generalize the sample to the full reachability set (or an overapproximation of it). We have implemented our method in a prototype tool which shows that our approach is competitive on a number of concrete examples. Furthermore, in contrast to all other existing regular model checking methods, termination is guaranteed in general for all systems with regular sets of reachable configurations. The method can be applied in a similar way to dealing with reachability relations instead of reachability sets too.     

A general type‐2 fuzzy model for computing with words

As a methodology, computing with words (CW) allows the use of words, instead of numbers or symbols, in the process of computing and reasoning and thus conforms more to humans’ inference when it is used to describe real‐world problems. In the line of developing a computational theory for CW, in this paper we develop a formal general type‐2 fuzzy model of CW by exploiting general type‐2 fuzzy sets (GT2 FSs) since GT2 FSs bear greater potential to model the linguistic uncertainty. On the one hand, we generalize the interval type‐2 fuzzy sets (IT2 FSs)‐based formal model of CW into general type‐2 fuzzy environments. Concretely, we present two kinds of general type‐2 fuzzy automata (i.e., general type‐2 fuzzy finite automata and general type‐2 fuzzy pushdown automata) as computational models of CW. On the other hand, we also give a somewhat universally general type‐2 fuzzy model of computing with (some special) words and establish a retraction principle from computing with words to computing with values for handling crisp inputs in general type‐2 fuzzy setting and a generalized extension principle from computing with words to computing with all words for handling general type‐2 fuzzy inputs.     

Stepwise development of fair distributed systems

A theory of fairness which supports the specification and development of a wide variety of “fair” systems is developed. The definition of fairness presented is much more general than the standard forms of weak and strong fairness, allowing the uniform treatment of many different kinds of fairness within the same formalism, such as probabilistic behaviour, for example. The semantic definition of fairness consists of a safety condition on finite sequences of actions and a liveness or termination condition on the fair infinite sequences of actions. The definition of the predicate transformer of a fair action system permits the use of the existing framework for program development, including the existing definitions of refinement and data refinement, thus avoiding an ad hoc treatment of fairness. The theory includes results that support the modular development of fair action systems, like monotonicity, adding skips, and data refinement. The weakest precondition and the weakest errorfree precondition are unified, so that in particular a standard action system is a special case of a fair action system. The results are illustrated with the development from specification of an unreliable buffer. Received: 3 January 2000 / 17 November 2002     

On-Line Multi-Threaded Paging

Abstract. In this paper we introduce a generalization of Paging to the case where there are many threads of requests. This models situations in which the requests come from more than one independent source. Hence, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. Four different on-line problems arise depending on whether we consider fairness restrictions or not, with finite or infinite input sequences. We study all of them, proving lower and upper bounds for the competitiveness of on-line algorithms. The main competitiveness results presented in this paper state that when no fairness restrictions are imposed it is possible to obtain competitive algorithms for finite and infinite inputs. On the other hand, for the fair case in general there exist no competitive algorithms. In addition, we consider three definitions of competitiveness for infinite inputs. One of them forces algorithms to behave efficiently at every finite stage, while the other two aim at comparing the algorithms' steady-state performances. A priori, the three definitions seem different. We study them and find, however, that they are essentially equivalent. This suggests that the competitiveness results that we obtain reflect the intrinsic difficulty of the problem and are not a consequence of a too strict definition of competitiveness.     

On-Line Multi-Threaded Paging

In this paper we introduce a generalization of Paging to the case where there are many threads of requests. This models situations in which the requests come from more than one independent source. Hence, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities. Four different on-line problems arise depending on whether we consider fairness restrictions or not, with finite or infinite input sequences. We study all of them, proving lower and upper bounds for the competitiveness of on-line algorithms. The main competitiveness results presented in this paper state that when no fairness restrictions are imposed it is possible to obtain competitive algorithms for finite and infinite inputs. On the other hand, for the fair case in general there exist no competitive algorithms. In addition, we consider three definitions of competitiveness for infinite inputs. One of them forces algorithms to behave efficiently at every finite stage, while the other two aim at comparing the algorithms' steady-state performances. A priori, the three definitions seem different. We study them and find, however, that they are essentially equivalent. This suggests that the competitiveness results that we obtain reflect the intrinsic difficulty of the problem and are not a consequence of a too strict definition of competitiveness.     

Relations rationnelles infinitaires

In this paper, we build a theory of infinitary rational relations, which is an extension of the theory of finitary rational relations, i. e. sets ofK-vectors of finite words which are recognized by finite automata withK tapes, and at the same time an extension of the theory of infinitary rational languages, i.e., sets of finite and infinite words which are recognized by finite automata (the condition of recognizability of an infinite word is that its reading by the automaton must go through a state, wich belongs to a designated subset, infinitly time). Our main result is a theorem similar to the Kleene theorem about rational languages of finite words: it is proved that the family of relations recognized by finite automata withK tapes is the family of relations obtained from the finite finitary relations with a finite sequence of operations of: union, product, finite star, and infinite star. Then the closure properties of this family of relations, are studied.      

Distance calculation on strings

A monoid of strings (words) over a finite alphabet is considered. The notion of distance on strings is important in the problem of inductive learning related to artificial intelligence, in cryptography, and in some other fields of mathematics. The distance is defined as a minimum length of the transformation path that transforms one string into another. One example is the Levenstein distance, with the transformations being insertions, deletions, and substitutions of letters. A quadratic algorithm for calculating this distance is known to exist. In this paper, a more general case—insertion and deletion of words of arbitrary length—is considered. For this case, the problem of distance calculation turns out to be unsolvable. The basic results of this work are the formulation of the condition of computability of distance and the algorithm for distance calculation, which is polynomial in string length.     

Testing avoidability on sets of partial words is hard

We prove that the problem of deciding whether a finite set of partial words is unavoidable is NP-hard for any alphabet of size larger than or equal to two, which is in contrast with the well-known feasability results for unavoidability of a set of full words. We raise some related questions on avoidability of sets of partial words.     

Synchronization of musical words

We study the synchronization of musical sequences by means of an operation defined on finite or infinite words called superimposition. This operation can formalize basic musical structures such as melodic canons and serial counterpoint. In the case of circular canons, we introduce the superimposition of infinite words, and we present an enumeration algorithm involving Lyndon words, which appear to be a useful tool for enumerating periodic musical structures. We also define the superimposition of finite words, the superimposition of languages, and the iterated superimposition of a language, which is applied to the study of basic aspects of serial music. This leads to the study of closure properties of rational languages of finite words under superimposition and iterated superimposition. The rationality of the transduction associated with the superimposition appears to be a powerful argument in the proof of these properties. Since the superimposition of finite words is the max operation of a sup-semilattice, the last section addresses the link between the rationality of a sup-semilattice operation and the rationality of the order relation associated with it.     

Schützenberger and Eilenberg theorems for words on linear orderings

This paper contains extensions to words on countable scattered linear orderings of two well-known results of characterization of languages of finite words. We first extend a theorem of Schützenberger establishing that the star-free sets of finite words are exactly the languages recognized by finite aperiodic semigroups. This gives an algebraic characterization of star-free sets of words over countable scattered linear orderings. Contrarily to the case of finite words, first-order definable languages are strictly included into the star-free languages when countable scattered linear orderings are considered. Second, we extend the variety theorem of Eilenberg for finite words: there is a one-to-one correspondence between varieties of languages of words on countable scattered linear orderings and pseudo-varieties of algebras. The star-free sets are an example of such a variety of languages.     

On the finite and general implication problems of independence atoms and keys

We investigate implication problems for keys and independence atoms in relational databases. For keys and unary independence atoms we show that finite implication is not finitely axiomatizable, and establish a finite axiomatization for general implication. The same axiomatization is also sound and complete for finite and general implication of unary keys and independence atoms, which coincide. We show that the general implication of keys and unary independence atoms and of unary keys and general independence atoms is decidable in polynomial time. For these two classes we also show how to construct Armstrong relations. Finally, we establish tractable conditions that are sufficient for certain classes of keys and independence atoms not to interact.     

Exponential lower bounds for the number of words of uniform length avoiding a pattern

We study words on a finite alphabet avoiding a finite collection of patterns. Given a pattern p in which every letter that occurs in p occurs at least twice, we show that the number of words of length n on a finite alphabet that avoid p grows exponentially with n as long as the alphabet has at least four letters. Moreover, we give lower bounds describing this exponential growth in terms of the size of the alphabet and the number of letters occurring in p. We also obtain analogous results for the number of words avoiding a finite collection of patterns. We conclude by giving some questions.     

LBlock结构的扩散层研究

最优扩散是分组密码扩散层优良的一个重要指标,Suzaki等人对GFS（广义Feistel结构）做了最优扩散的讨论,但对LBlock型结构的扩散层的最优扩散置换未见文献讨论。借助符号计算软件Mathematica 7.0,将LBlock的分块扩散路径用多项式表达出来,形式化分析此算法[P]层的扩散性。通过穷举所有可能的8元置换,证明了LBlock结构在8轮之前不能达到全扩散;不含移位操作的LBlock结构不能达到全扩散。并且验证了LBlock算法原有的置换[p[8]={2,0,3,1,6,4,7,5}]为最优扩散置换,最后得到了其他一些同样性质优良的置换。     

The Structure of Infinite Solutions of Marked and Binary Post Correspondence Problems

In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word ω such that h(ω) = g(ω). This problem is undecidable in general, but it is known to be decidable for binary and marked instances. A morphism is binary if the domain alphabet is of size 2, and marked if each image of a letter begins with a different letter. We prove that the solutions of a marked instance form a set E^ω ⋃ E^* (P ⋃ F), where P is a finite set of ultimately periodic words, E is a finite set of solutions of the PCP, and F is a finite set of morphic images of fixed points of D0L systems. We also establish the structure of infinite solutions of the binary PCP.     

On the existence of regular approximations

We approximate context-free, or more general, languages using finite automata. The degree of approximation is measured, roughly speaking, by counting the number of incorrect answers an automaton gives on inputs of length m$m$ and observing how these values behave for large m$m$. More restrictive variants are obtained by requiring that the automaton never accepts words outside the language or that it accepts all words in the language. A further distinction is whether a given (context-free) language has a regular approximation which is optimal under the measure of approximation degree or an approximation which is arbitrarily close to optimal. We study closure and decision properties of the approximation measure.