Automata, Formal Languages and Algebraic Systems

The following sections are included:

• PREFACE

• CONTENTS

Partial operations occur in the algebraic description of partial recursive functions and Turing machines (cf. A. I. Mal'cev⁸). Similarly to total operations superposition operations can also be defined on sets of partial operations. A clone of partial operations is a set of partial operations defined on the same base set A which is closed under superposition and contains all total projections. The collection of all clones of partial operations defined on a set A forms a complete lattice. For a finite nonempty set A this lattice is atomic and dually atomic. A partial algebra is said to be strongly solid if every strong identity of is satisfied as a strong hyperidentity in , i.e. if it is satisfied after any replacement of operation symbols by derived term operations of of the corresponding arity. A clone C of partial operations is called strongly solidifyable if there is a partial algebra such that C is equal to the clone of all term operations of . In this paper we determine all minimal strongly solidifyable clones of partial operations defined on a finite nonempty set A.

In this paper we introduce a novel cryptosystem based on finite automata without outputs. For encryption and decryption the apparatus uses the same secret keys, which have the transition matrix of a key-automaton without outputs and with an initial state and final states. To each character in the character set of the plaintext there is one or more final states of the key automaton assigned. During encryption the plaintext is read in sequentially character by character and the key automaton assigns to each plaintext character a character string, whose length is adjustable within a given length range. The apparatus creates the ciphertext by linking these character strings together. During decryption the key automaton starting from the initial state reads in the ciphertext character by character and decryption is accomplished by linking together the plaintext characters associated with certain final states, which provides the plaintext in its original form.

A linear grammar with Büchi acceptance condition is a system

where (N, Σ, P, X₀) is an ordinary linear grammar with nonterminal alphabet N, terminal alphabet Σ, productions P and start symbol X₀, and R ⊆ N is a set of repeated nonterminals. Consider the set of all finite and infinite derivation trees rooted X₀ whose leaves are labeled with letters of the terminal alphabet and possibly the empty word. When the tree is infinite, we require that at least one nonterminal letter in R appears infinitely often as the label of a vertex along the unique infinite branch of the tree. The frontier of such a tree determines a finite or infinite word over Σ. The set of all such words is called the linear language of finite and infinite words generated by G. Using results from ^1–3 we provide an algebraic characterization of linear languages by rational operations. More specifically, we associate a Conway semiring-semimodule pair (S, V) with each alphabet Σ, where S is a semiring associated with Σ and V is the set of all subsets of infinite words over Σ of appropriate order type, and show that a set in V is linear if and only if it can be generated from certain simple elements of the semiring S by the rational operations.

Wolper associated a temporal logic to each class of (regular) languages. A different semantics for essentially the same logic was given by Ésik. Both approaches can be extended to trees resulting in families of branching time temporal logics with regular modalities. Here, we compare the two semantics of these branching time temporal logics and use this comparison to derive an algebraic characterization of their expressive power with respect to the Wolper-style semantics in terms of varieties of finite algebras. We also provide a game-theoretic characterization.

Let Z be the ring of integers. We will write Z_n for Z/_nZ. The zero-divisor graph of Z_n, denoted Γ(Z_n), is the graph whose vertices are the non-zero zero-divisors of Z_n with two distinct vertices joined by an edge when the product of the vertices is zero. Let f(λ, Γ(Z_n)) be the characteristic polynomial of Γ(Z_n). To n = 4p (n ≠ 8) and n = 9p (n ≠ 27) where p is a prime number, we find the characteristic polynomial f(λ, Γ(Z_n)), the number of distinct 4-cycles and the number of 2-matchings of Γ(Z_n).

In this paper normal forms for context-free grammars, namely position restricted grammars, are treated and their influence to the size of the description of languages are presented. We discuss and compare several types of position restricted grammars and minimal size of grammars, expressed by the number of rules, needed to generate a language. Several techniques for the transformation of given grammar to an equivalent grammar in required form are used to reach upper bounds of the possible increase of the size complexity of languages related to different types of the position restricted grammars.

We develop the theory of Gröbner bases on an algebra based on a well-ordered semigroup inspired by the discussions in Farkas et al.,^3,4 where the authors study multiplicative bases in an axiomatic way. We consider a reflexive semigroup with 0 equipped with a suitable well-order, and use it as a base of an algebra over a commutative ring, on which we develop a Gröbner basis theory.

Our framework is considered to be fairly general and unifies the existing Gröbner basis theories on several types of algebras (ref. ^1,6–10). We discuss a Gröbner basis theory from a view point of rewriting systems. We study behaviors of critical pairs in our situation and give a so-called critical pair theorem. We need to consider z-elements as well as usual critical pairs come from overlapping applications of rules.

The following sections are included:

• Introduction

• Definitions

• Normal Forms

• Relations to Other Language Classes

• Characterization and Decidability Results

• Closure Properties

• References

As special cases of deep pushdown automata, we discuss finitely expandable deep pushdown automata that always contain a bounded number of non-input symbols in their pushdown stores. Based on these automata, it establishes an infinite hierarchy of language families that coincides with the hierarchy resulting from matrix grammars of finite index. Thus finitely expandable deep pushdown automata can are an automaton counterpart to these grammars. It also follows that deleting transitions do not add more power to finitely expandable deep pushdown automata. In a final section, we suggest some open problems.

The Hamming distance between two words of equal length is the number of positions where the two words differ. This distance is extended to a distance between words and languages and to a maximal distance of words of given length and a language. We investigate these distances between words and various sets of primitive words and various sets of periodic words which have been introduced in the paper ITO/LISCHKE: Generalized periodicity and primitivity for words, Math. Log. Quart. 53, 2007. The distance from an arbitrary word to one of the sets of primitive words is not greater than one. In the opposite direction, from primitive words to nonprimitive words this distance may be greater, and we determine it exactly to the periodic words and to the semi-periodic words, depending from the lengths of the words and from the cardinality of the alphabet, as well as to the remaining sets of nonprimitive words if the alphabet has at least three letters.

In this article, we first discuss the Fine continuity and the Fine convergence in relation to the continuous convergence on [0,1). Subsequently, we treat computability and the effective Fine convergence for a sequence of functions with respect to the Fine topology. We prove that the Fine computability does not depend on the choice of an effective separating set and that the limit of a Fine computable sequence of functions under the effective Fine convergence is Fine computable. Finally, we generalize the result of Brattka, which asserts the existence of a Fine computable but not locally uniformly Fine continuous function.

The family of context-free grammars and languages are frequently used. Unfortunately several important languages are not context-free. In this paper a possible family of extensions is investigated. In our derivations branch-interchanging steps are allowed: language families obtained by context-free and permutation rules are analysed. In permutation rules both sides of the rule contain the same symbols (with the same multiplicities). The simplest permutation rules are of the form AB → BA. Various families of permutation languages are defined based on the length of non-context-free productions. Only semi-linear languages can be generated in this way, therefore these language families are between the context-free and context-sensitive families. Interchange lemmas are proven for various families. It is shown that the generative power is increasing by allowing permutation rules with length three instead of only two. Closure properties and other properties are also detailed.

One of the main reasons that context-free grammars are widely used is the fact that the concept of derivation trees fits to them very well. The left-most derivations play important role both in theory and practice. Unfortunately with left-most derivations only context-free languages can be derived even if the rules of the grammar are not context-free. In this paper we investigate derivation trees for context-sensitive grammars based on Penttonen's one-sided normal form. The concept of the presented derivation graphs are a kind of extension of the well-known context-free derivation-trees. Moreover it allows to define left-most derivations in context-sensitive grammars without loosing the efficiency of the derivations. These left-most derivations are not derivations in the usual sentential form sense. They are the generalizations of the classical (context-free) left-most derivations, in the way of constructing a derivation tree. Some examples and a new type of ambiguity are also shown.

Motivated by the way in which sentences of natural languages are analyzed in linguistics, types of automata are studied that work on extended alphabets which, in addition to the input symbols, also contain certain auxiliary symbols. The latter model the use of (morphological, syntactical, and semantical) categories in the process of analyzing sentences. The automata we consider work on so-called characteristic languages, that is, on languages that include auxiliary symbols. The proper language is obtained from a characteristic language by removing all occurrences of auxiliary symbols. By requiring that the automata are lexicalized, we restrict the lengths of blocks of auxiliary symbols that are admitted. We study the classes of proper languages for deterministic finite-state acceptors, pushdown automata, two-pushdown automata, and freely rewriting restarting automata that are lexicalized. In addition, we use a generalization of the notion of proper language to associate a (binary) transformation with a characteristic language. This leads to the study of transformations of a certain form for the above types of automata.

It is known that the family of prefix codes is closed under the initial literal shuffle operation. However, it has not been known whether or not other families of codes are closed under this operation. In this paper we investigate the initial literal shuffles of subsets of full uniform codes. We shall show that the initial literal shuffle operation preserves various properties of uniform codes under certain conditions. From this fact, we can construct more complicated uniform codes from simpler uniform codes by using the initial literal shuffle operation.