Jewels are Forever

We study defects affecting state transitions in sequential circuits. The fault-free circuit is modeled by a semiautomaton M, and ‘simple’ defects, called single faults, by a set S = {M1, …,Mk} of ‘faulty’ semiautomata. To define multiple faults from S, we need a binary composition operation, say ⊙, on semiautomata, which is idempotent, commutative, and associative. Thus, one has the free semilattice S⊙ generated by S. In general, however, the single faults are not independent; a finite set E of equations of the form Mii ⊙…⊙Mih = Mj1 ⊙…⊙Mjk describes the relations among them. The pair (S, E) is a finite presentation of the quotient semilattice S ⊙ /η, where η is the smallest semilattice congruence containing E. In this paper, we first characterize such abstract quotient semilattices. We then survey the known results about random-access memories (RAMs) for the Thatte-Abraham fault model consisting of stuck-at, transition, and coupling faults. We present these results in a simplified semiautomaton model and give new characterizations of two fault semilattices.

A finite-state machine is called a Thompson machine if it can be constructed from a regular expression using Thompson’s construction. We assign distinct bracket pairs to the source and target states of all machine units that make up a Thompson machine. Each path from the start state to the final state of such a Thompson machine spells out a Dyck string. The collection of all such Dyck strings is the Thompson language of the given machine and the collection of such strings that are spelled out by simple paths is the simple Thompson language of the given machine. We characterize simple Thompson languages and Thompson languages, and we investigate their relationship.

In [5], the directable non deterministic automata are studied. For non-deterministic automata, the directability can be defined in several ways. In each case considered, the directing words constitute a regular language and one can study the families of such regular languages. In this paper, six classes of regular languages are defined in accordance with the different definitions of directability given in [5], and we investigate the properties of the classes considered.

New representation results for three families of regular languages are stated, using a special kind of shuffle operation, namely the synchronized shuffle. First, it is proved that the family of regular star languages is the smallest family containing the language (a + bc)* and closed under synchronized shuffle and length preserving morphism. The second representation result states that the family of ε-free regular languages is the smallest family containing the language (a + bc)*d and closed under synchronized shuffle, union and length preserving morphism. At last, it is proved that Reg is the smallest family containing the two languages (a+ bb)* and a+(ab)+, closed under synchronized shuffle, union and length preserving morphism.

Synchronization expressions are defined as restricted regular expressions that specify synchronization constraints between parallel processes and their semantics is defined using the synchronization languages. In this paper we survey results on synchronization languages, in particular, various approaches to obtain a characterization of this language family using closure under a set of rewriting rules. Also, we discuss the use and implementation of synchronization expressions in a programming language designed for a parallel or distributed computing environment.

Uniformizing a relation belonging to some family, consists of finding a function whose graph belongs to that family and whose domain coincides with that of the given relation. Here we focus on relations on finite or infinite strings that can be recognized by some version of finite automata.Eilenberg showed thatr ational relations of finite strings have the uniformazation property. We examine how this result can or cannot be extended. We show that given a length preserving n-ary rational relation and one of its component it can be uniformized, when viewed as a binary relation froma this component to the remaining components, and that binary deterministic relations also have the uniformization property. Finally, we shall show that rational relations on infinite strings can be uniformized.

The tree languages accepted by (finite state) tree-walking automata are known to form a subclass of the regular tree languages which is not known to be proper. They include all locally first-order definable tree languages. We allow the tree-walking automaton to use a finite number of pebbles, which have to be dropped and lifted in a nested fashion. The class of tree languages accepted by these tree-walking pebble automata contains all first-order definable tree languages and is still included in the class of regular tree languages. It also contains all deterministic top-down recognizable tree languages.

We give a brief survey of the (un)decidable properties of multicounter machines. In particular, we present some of the strongest decidable results (concerning emptiness, containment, and equivalence) known to date regarding these machines. We also discuss some applications.

This paper discusses on several variants of a fascinating problem of deciding whether two finite substitutions are equivalent on a regular language, as well as its relations to the equivalence problems of sequential transducers. Among other things it is proved to be decidable whether for a regular language L and two substitutions ϕ and ψ the latter one being a prefix substitution, the relation Unknown control sequence φ(w) ⊆ ψ (w) holds for all w in L.

As an alternative to the two classical proofs for complementation of Büchi automata, due to Büchi himself and to McNaughton, we outline a third approach, based on stratified alternating automata with a “weak” acceptance condition. Building on work by Muller, Saoudi, Schupp (1986) and Kupferman and Vardi (1997), we present a streamlined version of this complementation proof. An essential point is a determinacy result on infinite games with a weak winning condition. In a unifying logical setting, the three approaches are shown to correspond to three different types of second-order definitions of ω-languages.

We study the family of languages accepted by the integer weighted finite automata. Especially the closure properties of this family are investigated.

We use the framework of the monograph ”Semirings, Automata, Languages” by Kuich and Salomaa to study bounded languages and algebraic series having bounded supports. We characterize A-algebraic series having bounded supports in the case A is a subring of the real numbers or a positive semiring. This result implies the wellknown characterization of bounded context-free languages and shows that the characterization holds true for languages of finite degree of ambiguity even if multiplicities are counted.

We introduce full abstract families of tree series and show that their yields form full abstract families of power series that are closed under algebraic transductions. In the language case, the yield of a full abstract family of tree languages forms a full abstract family of languages that is closed under context-free substitutions.

We consider partial functions from a free monoid A to a field K and define a natural notion of periodicity in terms of linear semiautomata. We introduce the notion of greatest common divisor of two linear semiautomata and prove its existence and uniqueness. If a partial function is periodic with respect to two linear semiautomata A₁ and A₂ then, under suitable conditions on its domain, it is also periodic with respect to the greatest common divisor of A₁ and A₂. As a corollary of this result one obtains a generalization of Fine and Wilf’s periodicity theorem and a stronger version of Eilenberg Equality Theorem for rational series.

Evolutionary grammars form a grammatical model for the evolution of genomes where the basic derivation steps correspond to mutation in genomes. The generated language consists of all words which can be generated from the axioms (a finite set of words) by iterated derivation steps.In this paper we study the number of axioms, the number of mutations and the size of the mutations which are necessary in order to generate some languages. Especially we show that these parameters cannot be bounded in order to generate all possible languages.Furthermore we study the function which gives the number of words which can be generated by a certain number of derivation steps. We present some bounds and examples for such functions.

With motivations from various areas, in several places mechanisms based on iterated (non-deterministic) finite state sequential transducers were considered. It is known that such mechanisms can characterize the family of recursively enumerable languages. We continue here the study of such devices, investigating the hierarchy on the number of states. We find that this hierarchy collapses: four states are enough in order to characterize the recursively enumerable languages, three states cover the ETOL languages, while two states can cover the EOL (hence also context-free) languages. The case of deterministic transducers remains open.

Some first steps are proposed for a general approach to the structure and typology of formal languages in respect to the length of their words. A special attention is paid to the asymptotic behavior of various parameters involved in this problem.

This review paper will report on some recent discoveries in the area of Formal Languages, chiefly by F. Otto, G. Buntrock and G. Niemann. These discoveries have pointed out certain break-throughs connected with the concept of growing context-sensitive languages, which originated in the 1980’s with a paper by E. Dahlhaus and M.K. Warmuth. One important result is that the deterministic growing context-sensitive languages turn out to be identical to an interesting family of formal languages definable in a certain way by confluent reduction systems.

We introduce a new controlled DT0L system, called a word length controlled DT0L system, or a wlcDT0L system for short. A wlcDT0L system is a DT0L system with a control function which maps from the set of nonnegative integers to the set of tables. A wlcDT0L system derives exactly one word from a given word by iterating the table which is the value of the control function of the length of the given word. Thus a wlcDT0L system generates a sequence of words which starts from the axiom. We prove that every wlcPDT0L system generates a slender language. We also prove that there is a wlcDT0L language which is not slender. Since a slender language is applicable to cryptography, the family of wlcPDT0L languages may be useful for cryptography.

A theorem of Solovay states that there is a noncomputable Δ₂0 real x = (x _n ) _n such that H(x _n ) ⩽ H(n) + O(1). We improve this result by showing there is a noncomputable c.e. real x with the same property. This answers a question concerning the relationship between the domination relation and program-size complexity of initial segments of reals (informally, a real x dominates a real y if from a good approximation of x from below one can compute a good approximation of y from below). Solovay proved that if x and y are two c.e. reals and y dominates x, then H(x _n ) ⩽ H(y _n ) + O(1). The result above shows that the converse is false, namely there are c.e. reals x and y such that H(x _n ) ⩽ H(y _n ) + O(1) and y does not dominate x.

The investigation of the possibility or the impossibility to efficiently compute approximations of hard optimization problems becomes one of the central and most fruitful areas of current algorithm and complexity theory. Currently, optimization problems are considered to be tractable if there exist randomized polynomial-time approximation algorithms that solve them with a reasonable approximation ratio. Our opinion is that this definition of tractable problems is still too hard. This is because one usually considers the worst-case complexity and what is really important is the complexity of algorithms on “natural” problem instances (real data coming from the practice). Nobody exactly knows what “natural” data are and how to mathematically specify them. But, what one can do is to try to separate the easy problem instances from the hard ones. The aim of this paper is to develop an approach going in this direction.More precisely, a concept for measuring the stability of approximation algorithms is presented. This concept is of theoretical and practical interest because it can be helpful to determine the border between easy problem instances and hard problem instances of complex optimization problems that do not admit polynomial-time approximation algorithms. We illustrate the usefulness of our approach in an exemplary study of the knapsack problem.

The incompressibility method is an elementary yet powerful proof technique. It has been used successfully in many areas, including average-case analysis of algorithms [14]. In this expository paper, we include several new simple average-case analyses to further demonstrate the utility and elegance of the method.

The compressed recognition problem consists in checking if an input word w is in a given language L, when we are only given a compressed representation of w. We present several new results related to language recognition problems for compressed texts. These problems are solvable in polynomial time for uncompressed words and some of them become NP-hard for compressed words.Two types of compression are considered: Lempel-Ziv compress and compression in terms of straight-line programs (or sequences of recurrencem, or context-free grammars generating single texts). These compreassions are polynomically related and most of our results apply to both of them.Denote by LZ(w) (SLP(w)) the version of a string w produced by Lempel-Ziv encoding (straight-line program). The complexity of the following problem is considered:given a compressed version (LZ(w) or SLP(w)) of the input word w, test the membership w ∈ L, where L is a formal language.The complexity depends on the type and description of the language L. Surprisingly the proofs of NP-hardness are in this area usually easier than the proof that a problem in NP.The membership problem is in DSPACE(n2) for general context-free sets L and in NSPACE(n) for linear languages. We show that for unary languages compressed recognition of context-free languages is NP-complete.We also briefly discuss some known results related to the membership problem for the string-matching languages and for languages related to string-matching: square-free wordsm, squares, palindromes, and primitive words.

Some algorithms for performing arithmetical operations, on line, and fit for parallel and concurrent computation are described and investigated. The algorithms are based on the continued fractions representation of numbers and the continued fraction representation is generalized so as to allow rational quotients (instead of integer quotients). This generalization is intended to minimize the delay in the output stream of quotients provided by the units when a continuous stream of quotients is received by them at input.

An infinite word x has finite index if the exponents of the powers of primitive words that are factors of x are bounded. F. Mignosi has proved that a Sturmian word has finite index if and only if the coefficients of the continued fraction development of its slope are bounded. Mignosi’s proof relies on a delicate analysis of the approximation of the slope by rational numbers. We give here a proof based on combinatorial properties of words, and give some additional relations between the exponents and the slope.

Boxes of a word w are suitable factors of w which allow one to reconstruct the entire word. The initial (resp. terminal) box h _w (resp. k _w ) is the shortest unrepeated prefix (resp. suffix) of w. A proper box is any factor of the kind asb, where a, b are letters and s is a bispecial factor of w, i.e. there exist letters x, x1, y, y1 ,x ≠ x1, y ≠ y1 for which sx,sx1,ys and y1s are factors of w. In a previous paper we proved that any word is uniquely determined by h_w, k _w and the set of proper boxes. In this paper we extend this theorem to the case of any language. Moreover, a further extension is made to the case of two-dimensional languages (picture languages).

We show that square Wang tiles can be simulated by triangular or hexagonal Wang tiles or by rotating hexagonal tiles. Hence the aperiodic set of 13 square Wang tiles recently constructed by the author yields the smallest known aperiodic sets of all considered types of tiles.

We consider word equations where each variable occurs at most twice (quadratic systems). The satisfiability problem is NP-hard (even for a single equation), but once the lengths of a possible solution are fixed, then there is a deterministic linear time algorithm to decide whether there is a corresponding solution. If the lengths of a minimal solution were at most exponential, then the satisfiability problem of quadratic systems would be NP-complete.In the second part we address the problem with regular constraints: The uniform version is PSPACE-complete. Fixing the lengths of a possible solution doesn’t make the problem much easier. The non-uniform version remains NP-hard (in contrast to the linear time result above). The uniform version remains PSPACE-complete.In the third part we show that for quadratic systems the exponent of periodicity is at most linear in the denotational length.

We study several sets of ω-trajectories that have the following properties: each of them defines an associative and commutative operation of w-words and, moreover, each of them satisfies a certain condition of fairness.

We study minimal forbidden factors in finite and infinite words. In the case of a finite word w we consider two parameters: the first counts the minimal forbidden factors of w and the second gives the length of the longest minimal forbidden factor of w. We prove sharp upper and lower bounds for both parameters. We prove also that the second parameter is related to the minimal period of w. In the case of an infinite word w we consider the following two functions: g_w(n) that counts the allowed factors of w of length n and f_w (n) that counts the minimal forbidden factors of w of length n. We address the following general problem: which informations about the structure of w can be derived from the pair (g_w,f_w)? We prove that these two functions characterize, up to the automorphism exchanging the two letters, the language of factors of any infinite Sturmian word.

In [10] we proved that a model for the guided homologous recombinations that take place during gene rearrangement in ciliates has the computational power of a Turing machine, the accepted formal model of computation. In this paper we change some of the assumptions and propose a new model that (i) allows recombinations between and within circular strands in addition to recombinations between linear and circular strands and within linear strands, (ii) relies on a commutative splicing scheme, and (iii) where all recombinations are reversible. We prove that the modified model, the reversible guided recombination system, has the computational power of a Turing machine. This indicates that, in principle, some unicellular organisms may have the capacity to perform any computation carried out by an electronic computer.

The paper analyzes some properties of decision rules in the framework of rough set theory and knowledge discovery systems. With every decision rule two conditional probabilities are associated called the certatinty and coverage factors, respectively. It is shown that these coefficients satisfy the Bayes’ theorem. This relationship can be used as a new approach to Bayesian reasoning, without referring to prior and posterior probabilities, inherently associated with classical Bayesian inference. Decision rules are implications and the relationship between implications and Bayes’ theorem first was revealed by Lukasiewicz in connection with his multivaled logic.