Generalized periodicity and primitivity for words

Starting from six kinds of periodicity of words we define six sets of words which are primitive in different senses and we investigate their relationships. We show that only three of the sets are external Marcus contextual languages with choice but none of them is an external contextual language without choice or an internal contextual language. For the time complexity of deciding any of our sets by one-tape Turing machines, n ² is a lower bound and this is optimal in two cases. The notions of roots and degrees of words and languages, which are strongly connected to periodicity and primitivity, are also considered, and we show that there can be an arbitrarily large gap between the complexity of a language and that of its roots. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Stochastic programming for optimizing bidding strategies of a Nordic hydropower producer

From the point of view of a price-taking hydropower producer participating in the day-ahead power market, market prices are highly uncertain. The present paper provides a model for determining optimal bidding strategies taking this uncertainty into account. In particular, market price scenarios are generated and a stochastic mixed-integer linear programming model that involves both hydropower production and physical trading aspects is developed. The idea is to explore the effects of including uncertainty explicitly into optimization by comparing the stochastic approach to a deterministic approach. The model is illustrated with data from a Norwegian hydropower producer and the Nordic power market at Nord Pool.     

Growth rates of power-free languages

We propose a new fast algorithm for calculating the growth rate of complexity for regular languages. Based on this algorithm, we develop an efficient universal method for estimating the upper bound of the growth rates for power-free languages. Through extensive computer-assisted studies we sufficiently improve all known upper bounds for growth rates of such languages, obtain a lot of new bounds, and discover some general regularities.     

On some sets of dictionaries whose ω ‐powers have a given

A dictionary is a set of finite words over some finite alphabet X. The ω ‐power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [10] the complexity of the set of dictionaries whose associated ω ‐powers have a given complexity. In particular, he considered the sets ??( Σ ⁰k) (respectively, ??( Π ⁰_k), ??( Δ ¹₁)) of dictionaries V ? 2* whose ω ‐powers are Σ ⁰_k‐sets (respectively, Π ⁰_k‐sets, Borel sets). In this paper we first establish a new relation between the sets ??( Σ ⁰₂) and ??( Δ ¹₁), showing that the set ??( Δ ¹₁) is “more complex” than the set ??( Σ ⁰₂). As an application we improve the lower bound on the complexity of ??( Δ ¹₁) given by Lecomte, showing that ??( Δ ¹₁) is in Σ ¹ ₂(2^2*)\ Π ⁰₂. Then we prove that, for every integer k ≥ 2 (respectively, k ≥ 3), the set of dictionaries ??( Π ⁰_k+1) (respectively, ??( Σ ⁰_{k +1})) is “more complex” than the set of dictionaries ??( Π ⁰_k) (respectively, ??( Σ ⁰_k)) (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

逻辑,语义和计算机科学中的一些基本思想

本文对理论计算机科学，特别是对其在逻辑与语义方面的基本思想作了一个直观易懂的综述，旨在使上述思想为希望在该领域开拓视野之士敞开大门。     

A Tightly Integrated Modelling and Optimisation Library: A New Framework for Rapid Algorithm Development

The development of mathematical programming algorithms and heuristics has traditionally been hampered by the separation of modeller and optimiser. Developers either have to sacrifice performance by switching between a modeller and optimiser and communicating through cumbersome matrix files; or they can work solely with the in-core matrix in the optimiser, where knowledge about the structured algebraic model is missing and thus difficult to exploit.We present EMOSL, a new combined modelling and optimisation subroutine library that overcomes these drawbacks. It allows the problem to be manipulated using the notation of the model language, which is of course close to the algebraic formulation of the problem. Access is provided directly to the in-core matrix of the optimiser, eliminating the need to communicate via files. Thus the scope and ease of algorithm development is greatly improved, without any degradation of performance.We substantiate these claims by describing four applications: a block structure extraction tool, and the implementations of three MIP heuristics and cutting planes techniques.     

A spectrum handoff scheme for optimal network selection in Cognitive Radio vehicular networks: A game theoretic auction theory approach

The recent strides in vehicular networks have emerged as a convergence of multi radio access networks having different user preferences, multiple application requirements and multiple device types. In future Cognitive Radio (CR) vehicular networks deployment, multiple radio access networks may coexist in the overlapping areas having different characteristics in terms of multiple attributes. Hence, it becomes a challenge for CR vehicular node to select the optimal network for the spectrum handoff decision. A game theoretic auction theory approach is interdisciplinary effective approach to select the optimal network for spectrum handoff. The competition between different CR vehicular node and access networks can be formulated as multi-bidder bidding to provide its services to CR vehicular node. The game theory is the branch of applied mathematics which make intelligent decision to select the optimal alternative from predetermined alternatives. Hence, this paper investigates a spectrum handoff scheme for optimal network selection using game theoretic auction theory approach in CR vehicular networks. The paper has also proposed a new cost function based multiple attribute decision making method which outperforms other existing methods. Numerical results revel that the proposed scheme is effective for spectrum handoff for optimal network selection among multiple available networks.     

Growth and ergodicity of context-free languages

A language over a finite alphabet is called growth-sensitive if forbidding any set of subwords yields a sublanguage whose exponential growth rate is smaller than that of . It is shown that every ergodic unambiguous, nonlinear context-free language is growth-sensitive. ``Ergodic' means for a context-free grammar and language that its dependency di-graph is strongly connected. The same result as above holds for the larger class of essentially ergodic context-free languages, and if growth is considered with respect to the ambiguity degrees, then the assumption of unambiguity may be dropped. The methods combine a construction of grammars for -block languages with a generating function technique regarding systems of algebraic equations.

     

Linear splicing and syntactic monoid

Splicing systems were introduced by Head in 1987 as a formal counterpart of a biological mechanism of DNA recombination under the action of restriction and ligase enzymes. Despite the intensive studies on linear splicing systems, some elementary questions about their computational power are still open. In particular, in this paper we face the problem of characterizing the proper subclass of regular languages which are generated by finite (Paun) linear splicing systems. We introduce here the class of marker languages L, i.e., regular languages with the form L=L₁[x]₁L₂, where L₁,L₂ are regular languages, [x] is a syntactic congruence class satisfying special conditions and [x]₁ is either equal to [x] or equal to [x]∪{1}, 1 being the empty word. Using classical properties of formal language theory, we give an algorithm which allows us to decide whether a regular language is a marker language. Furthermore, for each marker language L we exhibit a finite Paun linear splicing system and we prove that this system generates L.