Automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science and discrete mathematics. The word automata comes means self-making
Alternating automata , the weak monadic theory of the tree, and its complexity
free download
The study of automata on infinite trees rests on the fundamental articles of Rabin [ 4]. In Rabin gave an ingeneous characterization of weakly definable languages and our proof uses one direction of his result in an essential way. We thus begin with a discussion of
Complexity of some problems from the theory of automata
free download
1.1. Given a finite alphabet L, the regular events over X are those accepted by a finite-state automaton. By Kleenes theorem, a subset W of S* is a regular event if and only if it can be constructed from the finiteword sets by boolean operations together with concatenation and
Mathematical foundations of automata theory
free download
Kleenes theorem is usually considered as the starting point of automata theory . It shows that the class of recognisable languages (that is, recognised by finite automata ), coincides with the class of rational languages, which are given by rational expressions. Rational expressions
A theory of timed automata
free download
Abstract Alur, R. and DL Dill, A theory of timed automata , Theoretical Computer Science 126 We propose timed (je) automata to model the behavior of real-time systems over time. Our definition provides a simple, and yet powerful, way to annotate state
The complexity of decision problems in automata theory and logic.
free download
The inherent computational complexity of a variety of decision problems in mathematical logic and the theory of automata is analyzed in terms of Turing machine time and space and in terms of the comp1exity of Boolean networks. The problem of deciding whether a star-free
A structure theory of automata characterized by groups
free download
There are many articles discussing the structure of automata algebraically. In Flecks first article , an automorphism group of an automaton is introduced, and it is shown that direct product decomposability of a perfect automaton is equivalent to that of its automorphism
Theory of finite automata with an introduction to formal languages
free download
It often seems that mathematicians regularly provide answers well before the rest of the world finds reasons to ask the questions. The operation of the networks of relays used in the first computers is exactly described by Boolean functions. George Boole thereby made his
Alternating automata , the weak monadic theory of trees and its complexity
free download
Beginning with the fundamental article of Chandra et al. , the notation of alternation has clarified several results concerning the complexity of logical theories. Muller and Schupp extended the idea of alternation to automata working on trees. Although such automata are
Theory of automata and its application to psychology
free download
The first three lectures deal with language processlng. The objectlve is to understand natural language, especially of children. The emphasis~ s on granl and sefTIantics wi th the maln accent on semantics. The semantics will mainly be concerned ulith model-thBoret
AtoCC: learning environment for teaching theory of automata and formal languages
free download
The learning environment AtoCC is presented to be of use in teaching abstract automata , formal languages, and some of its applications in compiler construction. From a teachers perspective AtoCC aims to address a broad range of different learning activities forcing the
Decomposition of automata and enriched category theory
free download
Modelling and verification of real-time systems using timed automata : theory and practice
free download
During the last decade, model-checking techniques for the verification of timed system have been developed based on the theory of timed automata . The practical limitation in applying these techniques to industrial-size systems is the huge amount of time and memory needed INTRODUCTION The concept of isolated cut-points plays a foundarnental role in the theory of probabilistic autornata. The following problern, suggested by ( 1 J and by [~] is qui te natural: (1) Can one device an algorithm to decide, for every given probabil_! stic autornaton
On the algebraic theory of automata
free download
A serious bibliography of automata theory (even algebraic) contains some few hundred titles which might explain my not attempting to record all the progress that has been accomplished; the quality of these works either published or awaiting publication is, as a In this paper we intend to give an impression of some applications of the theories of semigroups and groups to the theory of automata . In fact we shall not really restrict ourselves to automata but rather consider such applications to other related areas in theoretical
Theory and applications of nonlinear cellular automata in VLSI design
free download
Abstract In recent years, Cellular Automata (CA) have been found as an attractive modeling tool for various applications, such as, pattern recognition, image processing, data compression, encryption and specially V LSI design test. However, for all such
Methods and theory of automata and languages
free download
Automata Theory is the science of the treatment of languages (sets of words over a finite alphabet) from an algorithmic and theoretical viewpoint; there are also connections to the corresponding subsets of natural numbers. Automata , grammars and expressions have
Theory and applications of additive cellular automata for reliable and testable VLSI circuit design
free download
The present thesis embodies the applications of Cellular Automata (CA) for designing reliable and testable VLSI circuits. The homogeneous structure of CA and its different phases of development are briefly reviewed. The theory of generating Error Correcting Code
Review of Theory of Automata (Salomaa, A.; 1969)
free download
Consider a machine with a finite number of states, and with a finite set of inputs X. Suppose each input causes a deterministic change of state. Then we know that we can describe by what is called a regular expression those sets of input sequences that carry such a machine
Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata , and vector addition systems
free download
It turns out that there exists a surprising connection between certain ideas from the areas listed in the title. In this announcement we try to briefly outline the connection and to state our principal results. Very roughly, we use concepts from formal language theory , group