In this paper it is argued that certain stimulus-response learning models which are adequate to represent finite automata (acceptors) are not adequate to represent noninitial state input-output automata (transducers). This circumstance suggests the question whether or not the behavior of animals if satisfactorily modelled by automata is predictive. It is argued in partial answer that there are automata which can be explained in the sense that their transition and output functions can be described (roughly, Hempel-type (...) covering law explanation) while their behaviors are in principle not predictable short of possession of their complete histories or of information concerning present internal states by indirect observation. (shrink)

In this paper we present a negative solution of counting problems for some classes slightly different from bounded arithmetic (▵ 0 sets). To get the results we study properties of chains of finite automata.

I would like to make some further clarifying remarks about the nature of learning machines, or finite automata as they are more generally known these days. It is clear from much that has recently been written on this subject that there are still many misunderstandings about their capacity and significance.

We give new examples of FA presentable torsion-free abelian groups. Namely, for every n2, we construct a rank n indecomposable torsion-free abelian group which has an FA presentation. We also construct an FA presentation of the group in which every nontrivial cyclic subgroup is not FA recognizable.

We consider games over a finite alphabet with Gurevich-Harrington's winning conditions and restraints as in Yakhnis-Yakhnis . The game tree, the Gurevich-Harrington's kernels of the winning condition and the restraints are defined by finite automata. We give an effective criterion to determine the winning player and an effective presentation of a class of finite automata defined winning strategies.Our approach yields an alternative solution to the games considered by Büchi and Landweber . The BL algorithm is (...) an important tool for solving effectively presented games. The differences between the BL and our algorithms are as follows. Our algorithm is uniformly applicable to winning sets that correspond to boolean combinations of BL winning conditions, while the BL algorithm requires a transformation of such boolean combinations into a single BL condition. Our algorithm directly applies to a larger class of game trees for a given game alphabet than does the BL one. We describe Büchi-Landweber's class of winning conditions in a more transparent way by using finite automata and Gurevich-Harrington's form of winning conditions. Our algorithms that determine the winner of the game and find a winning strategy, are based on a translation of the events in the game in terms of the transition table of the automaton representing the game. This automaton differs from the ones that represent BL winning conditions. Both algorithms need further investigation.The algorithm determining the winner in the game, can be used as a verifier of concurrent programs. This is because programs can be viewed as strategies in Gurevich-Harrington's games and program specifications could be regarded as winning conditions for such games. The algorithm which finds a winning strategy could be used as a basis for automated concurrent program design.The present paper is a sequel to Annals of Pure and Applied Logic 48 277–297. (shrink)

Theory of Computation -- Computation by Abstracts Devices.

We present an elementary three-pass algorithm for computing addition in Ostrowski numeration systems. When a is quadratic, addition in the Ostrowski numeration system based on a is recognizable by a finite automaton. We deduce that a subset of X⊆Nn is definable in, where Va is the function that maps a natural number x to the smallest denominator of a convergent of a that appears in the Ostrowski representation based on a of x with a nonzero coefficient if and only (...) if the set of Ostrowski representations of elements of X is recognizable by a finite automaton. The decidability of the theory of follows. (shrink)

Linear temporal logic is a widely used method for verification of model checking and expressing the system specifications. The relationship between theory of automata and logic had a great influence in the computer science. Investigation of the relationship between quantum finite automata and linear temporal logic is a natural goal. In this paper, we present a construction of quantum finite automata on finite words from linear-time temporal logic formulas. Further, the relation between quantum (...) class='Hi'>finite automata and linear temporal logic is explored in terms of language recognition and acceptance probability. We have shown that the class of languages accepted by quantum finite automata are definable in linear temporal logic, except for measure-once one-way quantum finite automata. (shrink)

The first of the authors is an engineer, the second a logician, and they have collaborated to produce a systematic and comprehensive treatise and textbook on the theory of automata—computing machines viewed abstractly—which presupposes only a slight familiarity with logic; there is a long first chapter which develops propositional and predicate logic; the stipulation of logical operators, the "nets" constructed therefrom, and their physical realization comprise the next two chapters. The representation of automata in input-output tables and flow (...) diagrams, and the study of operators in structures come next; the last two chapters concern various practical ways of synthesizing automata and measuring the complexity of logical nets. This is one of the series on logic and foundations of mathematics; the translation from Russian was edited by J. C. Shepherdson.—P. J. M. (shrink)

A structure has a (finite-string) automatic presentation if the elements of its domain can be named by finite strings in such a way that the coded domain and the coded atomic operations are recognised by synchronous multitape automata. Consequently, every structure with an automatic presentation has a decidable first-order theory. The problems surveyed here include the classification of classes of structures with automatic presentations, the complexity of the isomorphism problem, and the relationship between definability and recognisability.

The first of the authors is an engineer, the second a logician, and they have collaborated to produce a systematic and comprehensive treatise and textbook on the theory of automata—computing machines viewed abstractly—which presupposes only a slight familiarity with logic; there is a long first chapter which develops propositional and predicate logic; the stipulation of logical operators, the "nets" constructed therefrom, and their physical realization comprise the next two chapters. The representation of automata in input-output tables and flow (...) diagrams, and the study of operators in structures come next; the last two chapters concern various practical ways of synthesizing automata and measuring the complexity of logical nets. This is one of the series on logic and foundations of mathematics; the translation from Russian was edited by J. C. Shepherdson.—P. J. M. (shrink)

We explore a network architecture introduced by Elman (1988) for predicting successive elements of a sequence. The network uses the pattern of activation over a set of hidden units from time-step 25-1, together with element t, to predict element t + 1. When the network is trained with strings from a particular finite-state grammar, it can learn to be a perfect finite-state recognizer for the grammar. When the network has a minimal number of hidden units, patterns on the (...) hidden units come to correspond to the nodes of the grammar, although this correspondence is not necessary for the network to act as a perfect finite-state recognizer. We explore the conditions under which the network can carry information about distant sequential contingencies across intervening elements. Such information is maintained with relative ease if it is.. (shrink)

We extend some of the classical connections between automata and logic due to Büchi [5] and McNaughton and Papert [12] to languages of finitely varying functions or “signals”. In particular, we introduce a natural class of automata for generating finitely varying functions called ’s, and show that it coincides in terms of language definability with a natural monadic second-order logic interpreted over finitely varying functions Rabinovich [15]. We also identify a “counter-free” subclass of ’s which characterise the first-order (...) definable languages of finitely varying functions. Our proofs mainly factor through the classical results for word languages. These results have applications in automata characterisations for continuously interpreted real-time logics like Metric Temporal Logic Chevalier et al. [6] and [7]. (shrink)

We define a class of finite state automata acting on transfinite sequences, and use these automata to prove that no singular cardinal can be defined by a monadic second order formula over the ordinals.