Stateless multicounter 5′?→?3′ Watson–Crick automata: the deterministic case

We consider stateless counter machines which mix the features of one-head counter machines and special two-head Watson?CCrick automata (WK-automata). These biologically motivated machines have heads that read the input starting from the two extremes. The reading process is finished when the heads meet. The machine is realtime or non-realtime depending on whether the heads are required to advance at each move. A counter machine is k -reversal if each counter makes at most k alternations between increasing mode and decreasing mode on any computation, and reversal bounded if it is k-reversal for some k. In this paper we concentrate on the properties of deterministic stateless realtime WK-automata with counters that are reversal bounded. We give examples and establish hierarchies with respect to counters and reversals.     

On the size of Boyer–Moore automata

In this work we study the size of Boyer–Moore automata introduced in Knuth, Morris & Pratt’s famous paper on pattern matching. We experimentally show that a finite class of binary patterns produce very large Boyer–Moore automata, and find one particular case which we conjecture, generates automata of size Ω(m⁶)$\Omega \left(m^6\right)$. Further experimental results suggest that the maximal size could be a polynomial of O(m⁷)$O\left(m^7\right)$, or even an exponential O(2^0.4m)$O\left(2^{0.4m}\right)$, where m$m$ is the length of the pattern.     

Watson–Crick palindromes in DNA computing

This paper provides an overview of existing approaches to encoding information on DNA strands for biocomputing, with a focus on the notion of Watson–Crick (WK) palindromes. We obtain a closed form for, as well as several properties of WK palindromes: The set of WK-palindromes is dense, context-free, but not regular, and is in general not closed under catenation and insertion. We obtain some properties that link the WK palindromes to classical notions such as that of primitive words. For example we show that the set of WK-palindromic words that cannot be written as the product of two nonempty WK-palindromes equals the set of primitive WK-palindromes. We also investigate various simultaneous Watson–Crick conjugate equations of words and show that the equations have, in most cases, only Watson–Crick palindromic solutions. Our results hold for more general functions, such as arbitrary morphic and antimorphic involutions.     

On the complexity of variations of mixed domination on graphs†

This paper is motivated by the concept of the mixed domination problem on graphs and dedicated to the complexity of variations of the problem such as the signed mixed domination, signed edge domination, minus mixed domination, and minus edge domination problems. In this paper, we present NP-completeness and MAX SNP-hardness results for some of them, and present a general framework of solving these problems and various dominating and covering problems for trees in linear time.     

The impact of alphabet size on pattern complexity of maxmin-$$omega$$ω cellular automata

Natural Computing - We present an analysis of an additive cellular automaton (CA) under asynchronous dynamics. The asynchronous scheme is maxmin-$$omega$$, a deterministic system, introduced in...     

Extended Watson–Crick L systems with regular trigger languages and restricted derivation modes

Watson?CCrick Lindenmayer systems add a control mechanism to ordinary Lindenmayer (L) system derivations. The mechanism is inspired by the complementarity relation in DNA strings, and it is formally defined in terms of a trigger language (trigger, for short). It is known that Watson?CCrick E0L systems employed with the standard trigger (which is a context-free language) are computationally universal. Here we show that all recursively enumerable languages can be generated already by a Uni-Transitional Watson?CCrick E0L system with a regular trigger. A system is Uni-Transitional if any derivation of a terminal word can apply the Watson?CCrick morphism at most once. We introduce a weak derivation mode where, for sentential forms in the trigger language, the derivation chooses nondeterministically whether or not to apply the Watson?CCrick morphism. We show that Watson?CCrick E0L systems employing a regular trigger and the weak derivation mode remain computationally universal but, on the other hand, the corresponding Uni-Transitional systems generate only a subclass of the ET0L languages. We consider also the computational power of Watson?CCrick (deterministic) ET0L systems.     

On �� 2 ? �� 2-products of automata

Two equivalent sufficient conditions are given for the completeness of classes of finite automata with respect to the isomorphic simulation under the ?? ₂ ? ?? ₂-product. It is conjectured that these conditions are also necessary with respect to the isomorphic or homomorphic simulation too.     

On the cost–effectiveness of PRAMs

We introduce a formalism which allows to treat computer architecture as a formal optimization problem. We apply this to the design of shared memory parallel machines. While present parallel computers of this type only support the programming model of a shared memory but often process simultaneous access by several processors to the shared memory sequentially, theoretical computer science offers solutions for this problem that are provably fast and asymptotically optimal. But the constants in these constructions seemed to be too large to let them be competitive. We modify these constructions under engineering aspects and improve the price/performance ratio by roughly a factor of 6. The resulting machine has surprisingly good price/performance ratio even if compared with distributed memory machines. For almost all access patterns of all processors into the shared memory, access is as fast as the access of only a single processor. Received: 29 June 1993 / 22 June 1999     

On the computation of Bernstein–Sato ideals

In this paper we compare the approach of Briançon and Maisonobe for computing Bernstein–Sato ideals—based on computations in a Poincaré–Birkhoff–Witt algebra—with the readily available method of Oaku and Takayama. We show that it can deal with interesting examples that have proved intractable so far.     

On the stability of the secular evolution of the planar Sun–Jupiter–Saturn–Uranus system

We investigate the long time stability of the Sun–Jupiter–Saturn–Uranus system by considering the planar, secular model. Our method may be considered as an extension of Lagrange’s theory for the secular motions. Indeed, concerning the planetary orbital revolutions, we improve the classical circular approximation by replacing it with a torus which is invariant up to order two in the masses; therefore, we investigate the stability of the elliptic equilibrium point of the secular system for small values of the eccentricities. For the initial data corresponding to a real set of astronomical observations, we find an estimated stability time of 10⁷ years, which is not extremely smaller than the lifetime of the Solar System (∼5 Gyr).     

The complexity of Boolean functions in the Reed–Muller polynomials class

This paper considers the problem of transforametion of Boolean functions into canonical polarized polynomials (Reed–Muller polynomials). Two Shannon functions are introduced to estimate the complexity of Boolean functions in the polynomials class under consideration. We propose three Boolean functions of n variables whose complexity (in terms of the number of terms) coincides with value. We investigate the properties of functions and propose their schematic realization on elements AND, XOR, and NAND.     

On some generalizations of the Thue–Morse morphism

In 1912, the Norwegian mathematician Axel Thue was the first to describe an overlap-free binary infinite word. This word was generated by a morphism which is called, since the works of Morse, the Thue–Morse morphism. Here, we present two generalizations of the Thue–Morse morphism in the case of alphabets with more than two letters. The extension of the characteristic properties of the word of Thue to the words generated by these morphisms is considered. One of these generalizations corresponds to the construction of Prouhet and a link with the Arshon words is given. In particular, we prove that if n is an even number then the n-letter Arshon word is generated by morphism.     

On the LAI of mixed soils–forests regions

In homogeneous forest textures, it has been recently confirmed experimentally that, for sufficiently large ground surfaces, the Leaf Area Index (LAI) has weak variations with respect to ground surface variations. This allows computing the LAI of mixed pixels on regions composed of forests and soils, with the use of the Perpendicular Vegetation Index (PVI). In the present paper, we study the accuracy of the method with experimental data.     

Simulation of a multitype Galton–Watson chain

We investigate the behaviour of a class of multitype Galton–Watson chains modelling the development of a genetic population. An algorithm for the computer generation of their trajectories is described and details concerning its implementation are given. We analyse through a simulation study the dependence of the extinction time of several populations on the initial gene frequencies and on the individual relative fertilities.     

On the security of the Kirchhoff-law–Johnson-noise (KLJN) communicator

A simple and general proof is given for the information theoretic (unconditional) security of the Kirchhoff-law–Johnson-noise key exchange system under practical conditions. The unconditional security for ideal circumstances, which is based on the second law of thermodynamics, is found to prevail even under slightly non-ideal conditions. This security level is guaranteed by the continuity of functions describing classical physical linear, as well as stable non-linear, systems. Even without privacy amplification, Eve’s probability for successful bit guessing is found to converge toward 0.5—i.e., the perfect security level—when ideal conditions are approached.     

Reachability analysis of reversal-bounded automata on series–parallel graphs

Acta Informatica - Extensions to finite-state automata on strings, such as multi-head automata or multi-counter automata, have been successfully used to encode many infinite-state non-regular...