Disjunctive languages related to p-primitive words

It is known that the set of all primitive words and the set of all $d$ -primitive words are disjunctive languages. In this paper we prove that the set of all $p$ -primitive words is disjunctive. We also prove that the set of all primitive but not $p$ -primitive words, the set of all balanced but not $p$ -primitive words, and the set of all $d$ -primitive but not $p$ -primitive words are disjunctive languages.     

On Empirical Meaning of Randomness with Respect to?Parametric Families of Probability Distributions

We study the a priori semimeasure of sets of P _θ -random infinite sequences, where P _θ is a family of probability distributions depending on a real parameter θ. In the case when for a computable probability distribution P _θ an effectively strictly consistent estimator exists, we show that Levin’s a priory semimeasure of the set of all P _θ -random sequences is positive if and only if the parameter θ is a computable real number. We show that the a priory semimeasure of the set è_qI_q\bigcup_{\theta}I_{\theta}, where I _θ is the set of all P _θ -random sequences and the union is taken over all algorithmically non-random θ, is positive.     

On a special class of primitive words

When representing DNA molecules as words, it is necessary to take into account the fact that a word u encodes basically the same information as its Watson-Crick complement θ(u), where θ denotes the Watson-Crick complementarity function. Thus, an expression which involves only a word u and its complement can be still considered as a repeating sequence. In this context, we define and investigate the properties of a special class of primitive words, called pseudo-primitive words relative to θ or simply θ-primitive words, which cannot be expressed as such repeating sequences. For instance, we prove the existence of a unique θ-primitive root of a given word, and we give some constraints forcing two distinct words to share their θ-primitive root. Also, we present an extension of the well-known Fine and Wilf theorem, for which we give an optimal bound.     

Special sequences as subcodes of reed-solomon codes

We consider sequences in which every symbol of an alphabet occurs at most once. We construct families of such sequences as nonlinear subcodes of a q-ary [n, k, n − k + 1] _q Reed-Solomon code of length n ≤ q consisting of words that have no identical symbols. We introduce the notion of a bunch of words of a linear code. For dimensions k ≤ 3 we obtain constructive lower estimates (tight bounds in a number of cases) on the maximum cardinality of a subcode for various n and q, and construct subsets of words meeting these estimates and bounds. We define codes with words that have no identical symbols, observe their relation to permutation codes, and state an optimization problem for them.     

From liveness to promptness

Liveness temporal properties state that something “good” eventually happens, e.g., every request is eventually granted. In Linear Temporal Logic (LTL), there is no a priori bound on the “wait time” for an eventuality to be fulfilled. That is, F θ asserts that θ holds eventually, but there is no bound on the time when θ will hold. This is troubling, as designers tend to interpret an eventuality F θ as an abstraction of a bounded eventuality F ^≤k θ, for an unknown k, and satisfaction of a liveness property is often not acceptable unless we can bound its wait time. We introduce here prompt-LTL, an extension of LTL with the prompt-eventually operator F _p . A system S satisfies a prompt-LTL formula φ if there is some bound k on the wait time for all prompt-eventually subformulas of φ in all computations of S. We study various problems related to prompt-LTL, including realizability, model checking, and assume-guarantee model checking, and show that they can be solved by techniques that are quite close to the standard techniques for LTL.     

Three-element codes with one d-primitive word

In the field of combinatorics on words, it is known that {u, v}, the language with two words is a code if and only if . But up to now general characterization for codes consisting of any three words has not been found. In 1998, Fan, Shyr and Yu provided a characterization for codes consisting of three d-primitive words. In this paper, we give characterizations for a code with three words in which one of the words is d-primitive.Received: 7 June 2004, Published online: 29 October 2004     

A theory of bisimulation for the π-calculus

 We study a new formulation of bisimulation for the π-calculus [MPW92], which we have called open bisimulation (∼). In contrast with the previously known bisimilarity equivalences, ∼ is preserved by allπ-calculus operators, including input prefix. The differences among all these equivalences already appear in the sublanguage without name restrictions: Here the definition of ∼ can be factorised into a “standard” part which, modulo the different syntax of actions, is the CCS bisimulation, and a part specific to the π-calculus, which requires name instantiation. Attractive features of ∼ are: A simple axiomatisation (of the finite terms), with a completeness proof which leads to the construction of minimal canonical representatives for the equivalence classes of ∼; an “efficient” characterisation, based on a modified transition system. This characterisation seems promising for the development of automated-verification tools and also shows the call-by-need flavour of ∼. Although in the paper we stick to the π-calculus, the issues developed may be relevant to value-passing calculi in general. Received: June 11, 1993/November 28, 1994     

Wetting of rough three-dimensional superhydrophobic surfaces

Wetting of rough three-dimensional periodic surfaces is studied. The contact angle of liquid with a rough surface (θ) is different from that with a smooth surface (θ₀) due to the difference in the contact area and effect of the air pockets. For non-wetting liquids (θ₀>π/2), the contact angle increases with roughness and may approach the value of π (superhydrophobic surface). For high θ₀, a homogeneous solid-liquid interface, as well as a composite solid-liquid-air interface with air pockets at the valleys of rough surface are possible. These two interfaces correspond to different states of equilibrium and result in different θ. A probability-based approach is introduced to handle the multiple states of equilibrium and to calculate θ. It is found also that increasing droplet size has the same effect as increasing period of roughness (size of asperities). For larger droplets and for larger asperities, the composite interface is less likely. For applications involving liquid’s transport near rough walls of a channel, an analogy between a droplet of non-wetting liquid and a gas bubble in wetting liquid is proposed. In order to increase bubbles mobility, the contact angle and the contact angle hysteresis should be minimized. Practical recommendations for design of superhydrophobic surfaces are formulated.     

Continuous-time quantum walks on semi-regular spidernet graphs via quantum probability theory

We analyze continuous-time quantum and classical random walk on spidernet lattices. In the framework of Stieltjes transform, we obtain density of states, which is an efficiency measure for the performance of classical and quantum mechanical transport processes on graphs, and calculate the spacetime transition probabilities between two vertices of the lattice. Then we analytically show that there are two power law decays ∼ t ⁻³ and ∼ t ^−1.5 at the beginning of the transport for transition probability in the continuous-time quantum and classical random walk, respectively. This results illustrate the decay of quantum mechanical transport processes is quicker than that of the classical one. Due to the result, the characteristic time t _c , which is the time when the first maximum of the probabilities occur on an infinite graph, for the quantum walk is shorter than that of the classical walk. Therefore, we can interpret that the quantum transport speed on spidernet is faster than that of the classical one. In the end, we investigate the results by numerical analysis for two examples.     

The sudden death of entanglement in constructed Yang–Baxter systems

Some Hamiltonians are constructed from the unitary \checkR_i,i+1(q, j){\check{R}_{i,i+1}(\theta, \varphi)}-matrices, where θ and j{\varphi} are time-independent parameters. We show that the entanglement sudden death (ESD) can happen in these closed Yang–Baxter systems. It is found that the ESD is not only sensitive to the initial condition, but also has a great connection with different Yang–Baxter systems. Especially, we find that the meaningful parameter j{\varphi} has a great influence on ESD.     

Semantics analysis through elementary meanings

Abstract. Thesaurus is a collection of words classified according to some relatedness measures among them. In this paper, we lay the theoretical foundations of thesaurus construction through elementary meanings of words. The concept of elementary meanings has been advocated and utilized in compiling Webster's Collegiate Thesaurus. If each word is supplied with elementary meanings so that all its meanings are covered by them in a standard fashion, we can define various similarity measures for a given set of words. Here we take an axiomatic way to analyze semantic structure of word groups. Assuming an abstract semantic world, we deduce closed sets as generalized synonym sets. That is, we show that under certain natural axioms, we only need to consider closed sets as far as the semantics are concerned. We also show that the set of generalized synonyms described as a certain pair of closed sets has a lattice structure. In order to have a flexible thesaurus, we also analyze structure changes corresponding to three basic environmental changes: A new word-meaning relation is added, a new word or a new meaning is included with its word-meaning relations. Actually we give algorithms to have updated lattice structure from previous one for the three operations. Received: 5 May 1996 / 21 February 2000     

New PCG based algorithms for the solution of Hermitian Toeplitz systems

In order to solve Toeplitz linear systems A_n(f)x=b generated by a nonnegative integrable function f, through use of the preconditioned conjugate gradient (PCG) method, several authors have proposed A_n(g) as preconditioner in the case where g is a trigonometric polynomial [10, 14, 27, 12, 28]. In preceding works, we studied the distribution and the extremal properties of the spectrum of the preconditioned matrix G=A _n ⁻¹ (g) A_n(f). In this paper we prove that the union of the spectra of all the G_n is dense on the essential range of f/g, i.e.,ER(f/g) and we obtain asymptotic information about the rate of convergence of the smallest eigenvalue λ _l ⁿ of G_n to r (and of λ _n ⁿ to R). As a consequence of this second order result, it is possible to handle the case where f has zeros of any order θ, through the PCG methods proposed in [10, 14]. This is a noteworthy extension since the techniques developed in [10, 14, 27, 12, 28] are shown to be effective only when f has zeros of even orders. The cost of this procedure is O(n^1+c(θ) log n) arithmetic operations (ops) where the quantity c(θ) belongs to interval [0,2⁻¹] and takes the maximum value 2⁻¹ when f has a zero of odd order. Finally, for the special case of zeros of odd orders, we propose a further algorithm which makes use of the PCG techniques proposed in [10, 14, 27, 12, 28] for theeven order case, reducing the cost to O(n long n) ops.     

On maximum norm contractivity of second order damped single step methods

In this paper we consider A(θ)-stable finite difference methods for numerical solutions of dissipative partial differential equations of parabolic type. Combining two rational approximation methods with different orders of accuracy, where the lower order method is applied n ₀ times (n ₀ fixed) at each time step, we prove the existence of a second order method which is contractive for all time steps. Moreover, we shed light on the conditions on the lower order method which are sufficient (and sometimes necessary) to obtain the optimal order of accuracy. For the one-dimensional heat equation we construct a family of numerical methods which are contractive in the maximum norm for all values of the discretization parameters. We also present numerical examples to illustrate our results. Received: May 2002 / Accepted: January 2003     

Unavoidable Sets of Partial Words

The notion of an unavoidable set of words appears frequently in the fields of mathematics and theoretical computer science, in particular with its connection to the study of combinatorics on words. The theory of unavoidable sets has seen extensive study over the past twenty years. In this paper we extend the definition of unavoidable sets of words to unavoidable sets of partial words. Partial words, or finite sequences that may contain a number of “do not know” symbols or “holes,” appear naturally in several areas of current interest such as molecular biology, data communication, and DNA computing. We demonstrate the utility of the notion of unavoidability of sets of partial words by making use of it to identify several new classes of unavoidable sets of full words. Along the way we begin work on classifying the unavoidable sets of partial words of small cardinality. We pose a conjecture, and show that affirmative proof of this conjecture gives a sufficient condition for classifying all the unavoidable sets of partial words of size two. We give a result which makes the conjecture easy to verify for a significant number of cases. We characterize many forms of unavoidable sets of partial words of size three over a binary alphabet, and completely characterize such sets over a ternary alphabet. Finally, we extend our results to unavoidable sets of partial words of size k over a k-letter alphabet. This material is based upon work supported by the National Science Foundation under Grant No. DMS-0452020. Part of this paper was presented at DLT’07 [4]. We thank the referees as well as Robert Mercaş and Geoffrey Scott for very valuable comments and suggestions. World Wide Web server interfaces have been established at and for automated use of the programs.     

Monte Carlo Estimation of a Joint Density Using Malliavin Calculus, and Application to American Options

We use the Malliavin integration by parts formula in order to provide a family of representations of the joint density (which does not involve Dirac measures) of (X_θ, X _{θ + δ}), where X is a d-dimensional Markov diffusion (d ≥ 1), θ > 0 and δ > 0. Following Bouchard et al. (2004), the different representations are determined by a pair of localizing functions. We discuss the problem of variance reduction within the family of separable localizing functions: We characterize a pair of exponential functions as the unique integrated-variance minimizer among this class of separable localizing functions. We test our method on the d-dimensional Brownian motion and provide an application to the problem of American options valuation by the quantization tree method introduced by Bally et al. (2002). MSC 1991 Subject Classifications: Primary 60H07 65C05, secondary 49-00     

A New view of the approximations in H v -groups

Let H is an H _v -group and the set of all finite products of elements of H. The relation β^* is the smallest equivalence relation on H such that the quotient H/ β^* is a group. The relation β^* is transitive closure of the relation β, where β is defined as follows: x β y if and only if for some . Based on the relation β, we define a neighborhood system for each element of H, and we presents a general framework for the study of approximations in H _v -groups. In construction approach, a pair of lower and upper approximation operators is defined. The connections between H _v -groups and approximation operators are examined.     

Inverse star, borders, and palstars

A language L is closed if L=L^?. We consider an operation on closed languages, L−?, that is an inverse to Kleene closure. It is known that if L is closed and regular, then L−? is also regular. We show that the analogous result fails to hold for the context-free languages. Along the way we find a new relationship between the unbordered words and the prime palstars of Knuth, Morris, and Pratt. We use this relationship to enumerate the prime palstars, and we prove that neither the language of all unbordered words nor the language of all prime palstars is context-free.     

An O(V 5/3 E 2/3) algorithm for the maximal flow problem

Summary A new algorithm for finding a maximal flow in a given network is presented. The algorithm runs in time O(V ^5/3 E ^2/3), where V and E are the number of the vertices and edges in the network. We use the notation A = 0(B) [A = Ω(B)] for A ≦ cB [A ≧ cB], and A = θ(B) for c ₁ B≦A ≦ c ₂ B where c, c ₁and c ₂are positive constants. (The same constants for all the occurrences of this notation)