Algebraic and structural automata theory. Transl. of algebraiczna i structuralna teoria automatów (PWN, Warsaw, 1985)
type: Item
instance of: scholarly article
title: Algebraic and structural automata theory. Transl. of algebraiczna i structuralna teoria automatów (PWN, Warsaw, 1985)
zbMATH Open document ID: 0717.68004
published in: Annals of Discrete Mathematics
publication date: 1993-01-23T00:00:00Z
review text: [The articles of this volume will not be indexed individually.] This monograph presents the work done in the seventies and the early eighties by a research group active at the Technical University of Poznan. We shall first describe briefly the twelve chaptes individually. Chapter 0 (Basic mathematical concepts by T. Gajewski; pp. 1-6) simply lists some basic mathematical concepts and notations. The aim of Chapter 1 (Automata and languages by J. Stoklosa; pp. 7-34) is to place the subject matter of the book into a larger context by reviewing briefly the Chomsky hierarchy and the relevant grammar and automata types. Chapter 2 (Finite automata by L. Beyga; pp. 35-82) introduces the Mealy, Moore and Rabin-Scott models of deterministic and nondeterministic finite automata, and regular languages along with several associated concepts. In Chapter 3 (Minimization of automata by B. Mikolajczak; 83-117) minimization algorithms for deterministic and incomplete automata are presented. The computational complexities of these problems are also considered. Chapter 4 (Input subautomata by J. Bergandy and Z. Miadowicz; pp. 119- 153) discusses automata obtained from a given automaton by changing the input and output alphabets so that these are formed by some input and output words, respectively, of the original automaton. When the alphabets are formed by all words of a fixed length k, such an input subautomaton may be regarded as a k-channel realization of the original automaton. In Chapter 5 (Automata homomorphisms by B. Mikolajczak; pp. 155-196) several notions of homomorphisms between automata are considered. Special attention is devoted to the computation of the homomorphisms between two given automata. Chapter 6 (Realizations of automata. State assignment by P. Siwak; pp. 197-228) considers ways to realize an automaton by another automaton or by a network of automata and the related problem of state assignments. The well-known approach of Hartmanis and Stearns based on SP partit…
reviewed by: Magnus Steinby
Mathematics Subject Classification ID: 68-06
Mathematics Subject Classification ID: 68-02
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 94C99
zbMATH DE Number: 44625
zbMATH Keywords: Structural automata theory
zbMATH Keywords: sequential machines. finite automata
zbMATH Keywords: regular languages
zbMATH Keywords: time-varying automata
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 44625