|
" Finite Automata, Formal Logic, and Circuit Complexity "
by Howard Straubing.
| Document Type
|
:
|
BL
|
| Record Number
|
:
|
726473
|
| Doc. No
|
:
|
b546205
|
| Main Entry
|
:
|
by Howard Straubing.
|
| Title & Author
|
:
|
Finite Automata, Formal Logic, and Circuit Complexity\ by Howard Straubing.
|
| Publication Statement
|
:
|
Boston, MA: Birkhäuser Boston : Imprint : Birkhäuser, 1994
|
| Series Statement
|
:
|
Progress in theoretical computer science.
|
| Page. NO
|
:
|
(xii, 227 pages)
|
| ISBN
|
:
|
1461202892
|
|
|
:
|
: 9781461202899
|
| Contents
|
:
|
I Mathematical Preliminaries --;I.1 Words and Languages --;I.2 Automata and Regular Languages --;I.3 Semigroups and Homomorphisms --;II Formal Languages and Formal Logic --;II. 1 Examples --;II. 2 Definitions --;III Finite Automata --;III. 1 Monadic Second-Order Sentences and Regular Languages --;III. 2 Regular Numerical Predicates --;III. 3 Infinite Words and Decidable Theories --;IV Model-Theoretic Games --;IV. 1 The Ehrenfeucht-Fraïssé Game --;IV. 2 Application to FO].
|
| Abstract
|
:
|
One of these, explored by McNaughton and Papert in their 1971 monograph Counter-free Automata, was the characterization of automata that admit first-order behavioral descriptions, in terms of the semigroup- theoretic approach to automata that had recently been developed in the work of Krohn and Rhodes and of Schiitzenberger.
|
| Subject
|
:
|
Computer science.
|
| Subject
|
:
|
Logic, Symbolic and mathematical.
|
| Subject
|
:
|
Mathematics.
|
| LC Classification
|
:
|
QA76.9.M35B946 1994
|
| Added Entry
|
:
|
Howard Straubing
|
| |