Formal and Natural Computing: Essays Dedicated to Grzegorz by Jean Berstel, Luc Boasson (auth.), Wilfried Brauer, Hartmut

By Jean Berstel, Luc Boasson (auth.), Wilfried Brauer, Hartmut Ehrig, Juhani Karhumäki, Arto Salomaa (eds.)

This ebook offers state-of-the-art examine in theoretical desktop technology and similar ?elds. particularly, the next components are mentioned: automata concept, formal languages and combinatorics of phrases, graph variations, Petri nets, concurrency, in addition to average and molecular computing. The articles are written through best researchers in those components. The writers have been initially invited to give a contribution to this ebook yet then the traditional refereeing strategy used to be utilized in addition. the entire articles take care of a few factor that has been lower than lively research in the course of fresh years. nonetheless, the subjects diversity from very classical ones to concerns raised in simple terms or 3 years in the past. either survey articles and papers attacking speci?c study difficulties are incorporated. The e-book highlights a few key problems with theoretical computing device technological know-how, as they appear to us now initially of the hot millennium. Being a complete review of a few of the main lively present examine in theoretical machine technological know-how, it may be of de?nite curiosity for all researchers within the parts lined. the subjects diversity from uncomplicated decidability and the inspiration of data to graph grammars and graph adjustments, and from bushes and strains to aqueous algorithms, DNA encoding and self-assembly. targeted e?ort has been given to lucid presentation. for that reason, the publication will be of curiosity additionally for complicated students.

Show description

By Jean Berstel, Luc Boasson (auth.), Wilfried Brauer, Hartmut Ehrig, Juhani Karhumäki, Arto Salomaa (eds.)

This ebook offers state-of-the-art examine in theoretical desktop technology and similar ?elds. particularly, the next components are mentioned: automata concept, formal languages and combinatorics of phrases, graph variations, Petri nets, concurrency, in addition to average and molecular computing. The articles are written through best researchers in those components. The writers have been initially invited to give a contribution to this ebook yet then the traditional refereeing strategy used to be utilized in addition. the entire articles take care of a few factor that has been lower than lively research in the course of fresh years. nonetheless, the subjects diversity from very classical ones to concerns raised in simple terms or 3 years in the past. either survey articles and papers attacking speci?c study difficulties are incorporated. The e-book highlights a few key problems with theoretical computing device technological know-how, as they appear to us now initially of the hot millennium. Being a complete review of a few of the main lively present examine in theoretical machine technological know-how, it may be of de?nite curiosity for all researchers within the parts lined. the subjects diversity from uncomplicated decidability and the inspiration of data to graph grammars and graph adjustments, and from bushes and strains to aqueous algorithms, DNA encoding and self-assembly. targeted e?ort has been given to lucid presentation. for that reason, the publication will be of curiosity additionally for complicated students.

Show description

Read or Download Formal and Natural Computing: Essays Dedicated to Grzegorz Rozenberg PDF

Best organization and data processing books

JDBC Recipes: A Problem-Solution Approach

JDBC Recipes offers easy-to-implement, usable suggestions to difficulties in relational databases that use JDBC. it is possible for you to to combine those recommendations into your web-based functions, equivalent to Java servlets, JavaServer Pages, and Java server-side frameworks. this useful e-book permits you to minimize and paste the strategies with none code adjustments.

The effects of sterilization methods on plastics and elastomers: the definitive user's guide and databook

This broadly up-to-date moment version used to be created for scientific equipment, scientific packaging, and nutrients packaging layout engineers, fabric product technical aid, and research/development group of workers. This finished databook includes very important features and homes info at the results of sterilization tools on plastics and elastomers.

Extra info for Formal and Natural Computing: Essays Dedicated to Grzegorz Rozenberg

Example text

Ehrenfeucht, R. Verraedt), 1980. 103. Fixed Point Languages, Equality Languages and Representation of Recursively Enumerable Languages, Journal of the ACM 27, 499–518 (with J. Engelfriet), 1980. 102. Tree Transducers, L Systems and Two-Way Machines, Journal of Computer and System Sciences 20, 150–202 (with J. Engelfriet, G. Slutzki), 1980. 101. Restrictions, Extensions and Variations of NLC Grammars, Information Sciences 20, 217–244 (with D. Janssens), 1980. 100. On the Structure of Node-Label Controlled Graph Languages, Information Sciences 20, 191–216 (with D.

Proof. Let q be the number of equivalence classes of L intersecting D. Let N be the width of L. Let u = u1 · · · un ∈ D∗ , with u1 , . . , un ∈ D. By a general result on congruences, [u1 ] · · · [un ] ⊂ [u] If n > N , then u is the equivalence class of words that are not factors of L. Otherwise, [u] contains at least one of the q + q 2 + · · · q N products of equivalence classes. Thus the number of equivalence classes of L intersecting D∗ is bounded by this number. The proposition is false if the width is unbounded.

Vn ∈ D. There exists a unique word X1 · · · Xn ∈ V ∗ such that ∗ ∗ S −→ gX1 · · · Xn d for some words g, d and some axiom S, and Xi −→ vi . We denote this word X1 · · · Xn by X(u). Define an equivalence relation on words in D∗ by u ∼ v if and only if X(u) ≡RX,a X(v) for all X ∈ V and a ∈ A. Here ≡RX,a is the syntactic congruence of the language RX,a . Since the sets RX,a are regular, there are only finitely many equivalence class for ∼. We show that u ∼ v implies u ≡L v. This shows that the set of Dyck words that are factors of words in L are contained in a finite number of classes for ≡L .

Download PDF sample

Rated 4.25 of 5 – based on 13 votes