Bulletin of the American Mathematical Society

MathSciNet review: 1567977
Full text of review: PDF   This review is available free of charge.
Book Information:

Author: 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.

[1]

A. Aho, R. Sethi, and J. Ullman, Compilers: Principles, techniques and tools, Addison-Wesly, Reading, MA, 1986.

David A. Mix Barrington and Denis Thérien, Finite monoids and the fine structure of $\textrm {NC}^1$, J. Assoc. Comput. Mach. 35 (1988), no. 4, 941–952. MR 1072406, DOI 10.1145/48014.63138

J. Richard Büchi, Weak second-order arithmetic and finite automata, Z. Math. Logik Grundlagen Math. 6 (1960), 66–92. MR 125010, DOI 10.1002/malq.19600060105

J. Richard Büchi, Regular canonical systems, Arch. Math. Logik Grundlag. 6 (1964), 91–111 (1964). MR 169410, DOI 10.1007/BF01969548

[5]

N. Chomsky, Three models for the description of language, IRE Trans. Inform. Theory 2 (1956), 113-124.

Noam Chomsky, On certain formal properties of grammars, Information and Control 2 (1959), 137–167. MR 105365

Samuel Eilenberg, Automata, languages, and machines. Vol. A, Pure and Applied Mathematics, Vol. 58, Academic Press [Harcourt Brace Jovanovich, Publishers], New York, 1974. MR 0530382

[8]

B. W. Kernighan and R. Pike, The UNIX programming environment, Prentice Hall, Englewood Cliffs, NJ, 1984.

S. C. Kleene, Representation of events in nerve nets and finite automata, Automata studies, Annals of Mathematics Studies, no. 34, Princeton University Press, Princeton, N.J., 1956, pp. 3–41. MR 0077478

Kenneth Krohn and John Rhodes, Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines, Trans. Amer. Math. Soc. 116 (1965), 450–464. MR 188316, DOI 10.1090/S0002-9947-1965-0188316-1

J.-E. Pin, Varieties of formal languages, Foundations of Computer Science, Plenum Publishing Corp., New York, 1986. With a preface by M.-P. Schützenberger; Translated from the French by A. Howie. MR 912694, DOI 10.1007/978-1-4613-2215-3

Amir Pnueli, The temporal logic of programs, 18th Annual Symposium on Foundations of Computer Science (Providence, R.I., 1977) IEEE Comput. Sci., Long Beach, Calif., 1977, pp. 46–57. MR 0502161

Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1

Emil L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1–11. MR 20527, DOI 10.2307/2267170

Michael O. Rabin, Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141 (1969), 1–35. MR 246760, DOI 10.1090/S0002-9947-1969-0246760-1

[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.

M. P. Schützenberger, On the definition of a family of automata, Information and Control 4 (1961), 245–270. MR 135680

J. W. Thatcher and J. B. Wright, Generalized finite automata theory with an application to a decision problem of second-order logic, Math. Systems Theory 2 (1968), 57–81. MR 224476, DOI 10.1007/BF01691346

[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.

[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.