|
Book Review
The AMS does not provide abstracts of book reviews.
You may download the entire review from the links below.
Retrieve article in:
PDF
Book Information
Author(s):
J. Richard B\"uchi
Title:
Finite automata, their algebras and grammars: Towards a theory of formal expressions
Additional book information:
Dirk Siefkes, editor, Springer-Verlag, New York, 1988, 316 pp., US$69.50. ISBN 3-540-96905-5
References:
-
- [1]
- A. Aho, R. Sethi, and J. Ullman, Compilers: Principles, techniques and tools, Addison-Wesly, Reading, MA, 1986.
- [2]
- D. Mix Barrington and D. Thérien, Finite monoids and the fine structure of
 , J. Assoc. Comput. Mach. 35 (1988), 941-952. MR 1072406 (91i:68039) - [3]
- J. R. Büchi, Weak second-order arithmetic and finite automata, Z. Math. Logik Grundlag. Math. 6 (1960), 66-92. MR 0125010 (23:A2317)
- [4]
- -, Regular canonical systems and finite automata, Arch. Math. Logik Grundlag. 6 (1964), 91-111. MR 0169410 (29:6660)
- [5]
- N. Chomsky, Three models for the description of language, IRE Trans. Inform. Theory 2 (1956), 113-124.
- [6]
- -, On certain formal properties of grammars, Inform. and Control 2 (1959), 137-167. MR 0105365 (21:4107)
- [7]
- S. Eilenberg, Automata, languages and machines, vol. B, Academic Press, New York, 1976. MR 0530383 (58:26604b)
- [8]
- B. W. Kernighan and R. Pike, The UNIX programming environment, Prentice Hall, Englewood Cliffs, NJ, 1984.
- [9]
- S. C. Kleene, Representations of events in nerve nets and finite automata, Automata Studies, (C. Shannon and J. McCarthy, eds.), Princeton Univ. Press, Princeton, NJ, 1956. MR 0077478 (17:1040c)
- [10]
- K. Krohn and J. Rhodes, The algebraic theory of machines I. Prime decomposition theorem for finite semigroups and machines, Trans. Amer. Math. Soc. 116 (1965), 450-464. MR 0188316 (32:5755)
- [11]
- J. E. Pin, Varieties of formal languages, Plenum, London, 1986. MR 912694 (89a:68125)
- [12]
- A. Pnueli, The temporal logic of programs, Proc. 18th Sympos. Found. Comput. Sci. IEEE Press, New York 1977, pp. 46-57. MR 0502161 (58:19311)
- [13]
- E. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284-316. MR 0010514 (6:29f)
- [14]
- -, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1-11. MR 0020527 (8:558b)
- [15]
- M. O. Rabin, Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141 (1969), 1-35. MR 0246760 (40:30)
- [16]
- S. Safra and M. Vardi, On
 -automata and temporal logic, Proc. 21st Sympos. Theory of Computing, ACM Press, New York, 1989, pp. 127-137. - [17]
- M. P. Schützenberger, On the definition of a family of automata, Inform. and Control 4 (1961), 245-270. MR 0135680 (24:B1725)
- [18]
- J. Thatcher and J. Wright, Generalized finite automata theory with an application to a decision problem of second-order logic, Math. Systems Theory 2 (1968), 57-81. MR 0224476 (37:75)
- [19]
- A. Thue, Die Lösung eines spezialfalles eines generallen logischen problems, Vidensdapssedkapet Skrifter Christiania, I. Math.-Nat. Klasse No. 8 (1910).
- [20]
- -, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Vidensdapssedkapet Skrister Christiania, I. Math.-Nat. Klasse No. 9 (1912).
- [21]
- -, Probleme über Veränderungen von Zeichenreihen nach gegebenen Regeln, Vidensdapssedkapet Skrifter Christiania, I. Math.-Nat. Klasse No. 10 (1914).
- [22]
- A. Turing, On computable numbers, with an application to the entscheidungsproblem, Proc. London Math. Soc. (2) 42 (1936), 230-265.
- [23]
- R. Wexelblat, ed., History of programming languages, Academic Press, New York, 1981.
Additional Information:
Reviewer(s):
Howard
Straubing
Review Information:
Journal:
Bull. Amer. Math. Soc.
26
(1992),
340-344.
DOI:
10.1090/S0273-0979-1992-00264-1
PII:
S 0273-0979(1992)00264-1
|
