Developments in Language Theory: Foundations, Applications, and Perspectives : Aachen, Germany, 6-9 July 1999The theory of formal languages is one of the oldest branches of theoretical computer science. Its original aim (in the fifties and sixties) was to clarify the laws and algorithms that underlie the definition and compilation of programming languages. Since then, formal language theory has changed very much. Today it includes mathematical topics like combinatorics of words, word equations, and coding theory, but it also covers connections to linguistics (for example, the study of contextual grammars), new computational paradigms (like DNA computing), and a wide range of applications, among them hypertext processing, database theory, and formal program verification. Many of these themes of modern formal language theory are represented in this volume. |
Contents
Special factors in some combinatorial structures | 3 |
On the decomposition of finite languages | 22 |
Asynchronous sliding block maps | 47 |
Bisimulations and behaviour of nondeterministic automata | 60 |
Functions preserving classes of languages | 81 |
Restarting automata ChurchRosser languages and representations | 103 |
Other editions - View all
Common terms and phrases
algorithm alphabet ambiguity automaton avoid the patterns bisimulation bounded series caterpillar cells closure collage grammars collage languages complexity components Computer Science consider constraint construct contains context-free grammar context-free languages context-sensitive context-sensitive languages contextual grammar defined Definition denoted derivation deterministic example exists factor Figure finite decomposition finite languages finite set Formal Languages FREG FREG,REG function f grammar G graph hyperedge infinite word input integer internal contextual languages interval exchange transformations L₁ labeled Lemma length linear grammar locally testable membership problem minimal monoid morphism node nondeterministic nonterminal notion obtain output Parikh parse tree prefix production Proposition prove pumping trees recursively regular languages resp restarting result rewriting Salomaa semigroups semilinear sequence set of trees simulation sliding block map string Sturmian words subset subword suffix symbol transducer transition tree automaton tree languages Turing machine UP-composite w₁


