Skip to main content
main-content

Über dieses Buch

Dedicated to Arto Salomaa, a towering figure of theoretical computer science, on the occasion of his 65th birthday, this book is a tribute to him on behalf of the theoretical computer science community. The contributions are written by internationally recognized scientists and cover most of Salomaa's many research areas. Due to its representative selection of classic and cutting edge trends in theoretical computer science, the book constitutes a comprehensive state-of-the-art survey.
The contributions are in such central areas as automata theory, algorithms and complexity, and combinatorics of words. But not only that, they take up new areas such as regular sets and biocomputing. While some are survey articles of fundamental topics, most are original research papers.

Inhaltsverzeichnis

Frontmatter

Automata I: Finite State Machines

Frontmatter

Semilattices of Fault Semiautomata

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.

Janusz A. Brzozowski, Helmut Jürgensen

Thompson Languages

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.

Dora Giammarresi, Jean-Luc Ponty, Derick Wood

On Some Special Classes of Regular Languages

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.

Balázs Imreh, Masami Ito

Synchronized Shuffle and Regular Languages

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.

Michel Latteux, Yves Roos

Synchronization Expressions: Characterization Results and Implementation

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.

Kai Salomaa, Sheng Yu

Automata II: More General Devices

Frontmatter

Uniformization of Rational Relations

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.

Christian Choffrut, Serge Grigorieff

Tree-Walking Pebble Automata

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.

Joost Engelfriet, Hendrik Jan Hoogeboom

Counter Machines: Decision Problems and Applications

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.

Oscar H. Ibarra, Jianwen Su

On the Equivalence of Finite Substitutions and Transducers

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.

Juhani Karhumäki, Leonid P. Lisovik

Complementation of Büchi Automata Revisited

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.

Wolfgang Thomas

Automata with Multiplicities

Frontmatter

Languages Accepted by Integer Weighted Finite Automata

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

Vesa Halava, Tero Harju

A Power Series Approach to Bounded Languages

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.

Juha Honkala

Full Abstract Families of Tree Series I

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.

Werner Kuich

Linear Automata, Rational Series and a Theorem of Fine and Wilf

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 A1 and A2 then, under suitable conditions on its domain, it is also periodic with respect to the greatest common divisor of A1 and A2. 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.

Giovanna Melideo, Cesidia Pasquarelli, Stefano Varricchio

Formal Languages

Frontmatter

Numerical Parameters of Evolutionary Grammars

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.

Jürgen Dassow

Iterated GSM Mappings: A Collapsing Hierarchy

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.

Vincenzo Manca, Carlos Martin-Vide, Gheorghe Päun

On the Length of Words

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.

Solomon Marcus

An Insertion into the Chomsky Hierarchy?

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.

Robert McNaughton

Word Length Controlled DT0L Systems and Slender Languages

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.

Taishin Yasunobu Nishida

Algorithms and Complexity

Frontmatter

Program-Size Complexity of Initial Segments and Domination Reducibility

A theorem of Solovay states that there is a noncomputable Δ20 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.

Cristian S. Calude, Richard J. Coles

Stability of Approximation Algorithms and the Knapsack Problem

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.

Juraj Hromkovič

Some Examples of Average-case Analysis by the Incompressibility Method

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.

Tao Jiang, Ming Li, Paul Vitányi

Complexity of Language Recognition Problems for Compressed Words

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.

Wojciech Plandowski, Wojciech Rytter

Algorithms on Continued Fractions

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.

Soldea Octavian, Azaria Paz

Combinatorics of Words

Frontmatter

On the Index of Sturmian Words

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.

Jean Berstel

Repetitions and Boxes in Words and Pictures

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 hw, 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).

Arturo Carpi, Aldo de Luca

Small Aperiodic Sets of Triangular and Hexagonal Tiles

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.

Karel Culik

Quadratic Word Equations

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.

Volker Diekert, John Michael Robson

Fair and Associative Infinite Trajectories

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.

Alexandru Mateescu, George Daniel Mateescu

Forbidden Factors in Finite and Infinite Words

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: gw(n) that counts the allowed factors of w of length n and fw (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 (gw,fw)? We prove that these two functions characterize, up to the automorphism exchanging the two letters, the language of factors of any infinite Sturmian word.

Filippo Mignosi, Antonio Restivo, Marinella Sciortino

Novel Directions

Frontmatter

Reversible Molecular Computation in Ciliates

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.

Lila Kari, Jarkko Kari, Laura F. Landweber

Logic, Probability, and Rough Sets

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.

Zdzisław Pawlak

Backmatter

Weitere Informationen