scientific article; zbMATH DE number 3311755
Durch die große Bedeutung, die die Theorie der formalen Sprachen sowohl in den Grundlagenuntersuchungen als auch in der mathematischen Kybernetik hat, vermittelt das Buch auf diesem Gebiet für Studenten dieser Disziplinen das notwendige Grundwissen. Es werden erstmalig die wichtigsten Ergebnisse der Theorie der formalen Sprachen in dieser Vollständigkeit dargestellt. Ausgehend von einem allgemeinen Algorithmenbegriff, der etwas zu kurz behandelt wird, werden die einzelnen Grammatiktypen definiert. Zu jedem Sprachtyp werden endliche Automaten ohne Ausgabe angegeben, die genau diese Sprache akzeptieren. Dabei werden verschiedene Automatentypen gegenübergestellt. Besondere Aufmerksamkeit schenken die Verff. den kontextfreien Sprachen, deren Grammatiken in den Normalformen von Chomsky und Greibach dargestellt werden. Ebenso ausführlich sind die Abschnitte über Turing-Maschinen gehalten. In ihnen werden einige Varianten von Turing-Maschinen untersucht und die von diesen akzeptierten Sprachen beschrieben. Wie üblich wird mit Hilfe einer universellen Turing-Maschine die Unentscheidbarkeit des \glqq Halteproblems\grqq{} gezeigt. Davon ausgehend werden für die einzelnen Sprachtypen die Unentscheidbarkeit einiger Eigenschaften (z.B. das Postsche Korrespondenzprinzip) nachgewiesen. Ferner wird untersucht, gegenüber welchen Operationen die Sprachklassen abgeschlossen sind. Vorteilhaft hat sich die parallele Entwicklung der Theorie der formalen Sprachen und der Automatentheorie erwiesen. Damit ist dieses Buch durch seine knappe und übersichtliche Darstellung sehr gut geeignet, das notwendige Grundwissen in der Theorie der formalen Sprachen zu vermitteln. Durch die einfachen, jedoch geschickt gewählten Beispiele werden wichtige Begriffsbildungen hervorgehoben. Besondere Beachtung ist den Übungsaufgaben zu schenken, wobei sich die Verff. bei. einer Neuauflage überlegen sollten, ob es nicht zweckmäßig ist, bei besonders schwierigen Aufgaben am Ende des Buches oder durch entsprechende Literaturhinweise eine Hilfe zu geben. Obwohl dieses Buch leicht verständlich geschrieben ist, ist es zweckmäßig, einige Vorkenntnisse auf den Gebieten Algorithmentheorie und Automatentheorie zu besitzen.
- Fault-tolerant computation of distributed regular path queries
- On small, reduced, and fast universal accepting networks of splicing processors
- Space complexity of abelian groups
- Malcev presentations for subsemigroups of direct products of coherent groups.
- Algorithms for learning regular expressions from positive data
- Primitivity of finitely presented monomial algebras.
- The 4-way deterministic tiling problem is undecidable
- Regular production systems and triangle tilings
- Deterministic finite automata with recursive calls and DPDAs
- Decimations of languages and state complexity
- Small overlap monoids. I: The word problem.
- Small overlap monoids. II: Automatic structures and normal forms.
- Space-filling curves in adaptive curvilinear coordinates for computer numerically controlled five-axis machining
- A formal approach to subgrammar extraction for NLP
- On NFAs where all states are final, initial, or both
- Detecting palindromes, patterns and borders in regular languages
- Theory of one-tape linear-time Turing machines
- Lattice-valued fuzzy Turing machines: computing power, universality and efficiency
- An axiom system for sequence-based specification
- Limitations of learning in automata-based systems
- Real functions and numbers defined by Turing machines
- A low and a high hierarchy within NP
- Analyse numérique du problème des ondes longues en eau peu profonde
- Init and Anf operating on \(\omega\)-languages
- A note on the parallel computation thesis
- Some undecidability results for non-monadic Church-Rosser Thue systems
- A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
- An application of the matrix representation of transductions
- The complexity of finding minimum-length generator sequences
- Alternating simple multihead finite automata
- Complexity and decidability for chain code picture languages
- Hierarchies of hyper-AFLs
- On proving time constructibility of functions
- Restrictions on NLC graph grammars
- Some results on subclass containment problems for special classes of dpda's related to nonsingular machines
- Depth-first search is inherently sequential
- The complexity of some decision problems about two-dimensional array grammars
- Robust algorithms: a different approach to oracles
- A linear time solution to the single function coarsest partition problem
- The smallest automaton recognizing the subwords of a text
- Exposure to deadlock for communicating processes is hard to detect
- Parallel and sequential transformations on digital images
- Square time is optimal for simulation of one pushdown store or one queue by an oblivious one-head tape unit
- Variations on the technique of Ďuriš and Galil
- An \(n^{1.618}\) lower bound on the time to simulate one queue or two pushdown stores by one tape
- Classes of regular and context-free languages over countably infinite alphabets
- Complexity results on the conjugacy problem for monoids
- Three-way automata on rectangular types over a one-letter alphabet
- Three-way two-dimensional finite automata with rotated inputs
- Random generation of combinatorial structures from a uniform distribution
- Recurrent words and simultaneous growth in T0L systems
- A pumping lemma for real-time deterministic context-free languages
- Pattern selector grammars and several parsing algorithms in the context- free style
- On the structure of one-tape nondeterministic Turing machine time hierarchy
- Alternating on-line Turing machines with only universal states and small space bounds
- The theory of ends, pushdown automata, and second-order logic
- Finite automata play the repeated prisoner's dilemma
- On solving star equations
- On the regular equivalence problem for regular Thue systems
- On \(\Delta ^ P_ 2\)-immunity
- The space complexity of the unique decipherability problem
- On pebble automata
- On the complexity of theories of permutations
- Approximation to measurable functions and its relation to probabilistic computation
- Microeconomic foundations of cyclical irregularities or chaos
- The problems of cyclic equality and conjugacy for finite complete rewriting systems
- Pushdown machines for the macro tree transducer
- A hierarchy of random-context grammars and automata
- Infinite streams and finite observations in the semantics of uniform concurrency
- The parallel complexity of deadlock detection
- The undecidability of self-embedding for finite semi-Thue and Thue systems
- Boolean delay equations. II: Periodic and aperiodic solutions
- A Yacc extension for LRR grammar parsing
- Concurrent program schemes and their logics
- Parallel parsing of programming languages
- Graph embedding in SYNCHEM2, an expert system for organic synthesis discovery
- High level tree transducers and iterated pushdown tree transducers
- A note on complete problems for complexity classes
- Several properties of array languages
- The membership and equivalence problems for picture languages
- On nondeterminism in parallel computation
- A classification of complexity core lattices
- The method of forced enumeration for nondeterministic automata
- Language complexity on the synchronous anonymous ring
- Two-dimensional iterative arrays: Characterizations and applications
- Automata accepting primitive words
- The interchange or pump (di)lemmas for context-free languages
- Some relationships between logics of programs and complexity theory
- Theory of traces
- Isomorphisms and 1-L reductions
- There are no fully space constructible functions between log log n and log n
- Remarks on string-matching and one-way multihead automata
- \(\Sigma_ 2SPACE(n)\) is closed under complement
- Tape versus queue and stacks: The lower bounds
- k\(+1\) heads are better than k for PDAs
- Parallel algorithms for solvable permutation groups
- Relativized alternation and space-bounded computation
- On sparse oracles separating feasible complexity classes
- Grammatical inference for even linear languages based on control sets
- On the relative complexity of hard problems for complexity classes without complete problems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5592246)