Arto Salomaa

Indeholder "Acknowledgements", "Preface", "1. Repetitions", " 1.1 Words and languages", " 1.2 Thue's problem", " 1.3 Solution to the strong cube-freeness problem", " 1.4 Solution to the square-freeness problem", " 1.5 Overlapping", " 1.6 DOL-systems and ω-words", "2. Regularity, characterizations", " 2.1 Representability", " 2.2 Finite deterministic automata", " 2.3 Regular expressions", " 2.4 Kleene's theorem", "3. Regularity: challenging problems", " 3.1 Star height", " 3.2 Finite power property", "4. Codes and equality sets", " 4.1 Characteristic properties of codes", " 4.2 Maximal codes", " 4.3 Codes with bounded delay", " 4.4 Equality sets and their regularity", " 4.5 Elementary morphisms", " 4.6 Post correspondence problem", "5. Decidable and undecidable", " 5.1 OL systems", " 5.2 DOL equivalence problems", " 5.3 Udecidability results", "6. Morphic representations", " 6.1 Local and regular languages", " 6.2 A morphic generator for context-free languages", " 6.3 Generation of recursively enumerable languages by morphisms", "7. Language families", " 7.1 Regular languages as a grammatical family", " 7.2 A dense hierarchy of grammatical families", " 7.3 Colorings and families of graphs", "Historical and Bibliographical Remarks", "References", "Index".

En klassiker i teoretisk datalogi. Sammenhænge mellem sprogklasser, endelige automater og diverse problemer, fx Post's korrespondanceproblem… (mehr)