Varieties of Formal Languages (Foundations of Computer Science) - Hardcover

Pin, J.E.

Hardcover

ISBN 10: 0306422948 ISBN 13: 9780306422942

Publisher: Springer, 1986

Synopsis

The theory of finite automata and of rational languages could be likened to the ground floor of a huge building under construction which is theoretical computer science. The metaphor would indicate first that it can be entered on the ground level and secondly that it is more convenient to go through it in order to reach the higher levels. It is also the first purely mathematical theory to emerge from the needs and intuitions of computer science in the wider sense. In fact, at the end of the 1950s Kleene, who was intrigued by electronic models of the nervous system which were then very fashionable, proposed characterizing feasible calculations by means of a system making use of a single bounded memory. This led him to discover what are now called rational languages which are the subject of the present book by J. E. Pin. Subsequent work has revealed that this class is a particularly fundamental mathematical entity in the study of finite systems, for they appear quite naturally starting from considerations as diverse as those of restricted logical systems or the standard rational functions of analysis. From the start, one of the principal problems was found to be a problem of classification, or rather of hierarchization. J. Rhodes showed that the compo sition of automata preserved the associated groups and McNaughton discovered that the existence of non-trivial groups of this kind was intimately related to the presence of loops within the system of calculation. The development by S."

About this title

Language Notes

Text: English, French (translation)

Edition details

• Publisher: Springer
• Publication date: 1986
• Language: English
• ISBN 10: 0306422948
• ISBN 13: 9780306422942
• Binding: Hardcover
• Edition number: 1
• Number of pages: 148