Developments in language theory. II. At the crossroads of mathematics, computer science and biology. Papers from the conference held in Magdeburg, Germany, July 17–21, 1995. (English) Zbl 0919.00068

Singapore: World Scientific. x, 491 p. (1996).

Show indexed articles as search result.

Contents: Christiane Bercoff, A family of \(p\)-uniform tag systems for \(p\)-paperfolding sequences (3-12);
Jean Berstel, Recent results in Sturmian words (13-24);
Julien Cassaigne, Special factors of sequences with linear subword complexity (25-34);
James D. Currie and Robert O. Shelton, Cantor sets and Dejean’s conjecture (35-43);
Lucian Ilie, On disjunctivity, ultimate periodicity and ultimate identity of Paun-Salomaa self-reading sequences (44-53);
Jarkko Kari and Valtteri Niemi, Colored Gauss and tangent codes on the torus (54-63);
Victor Mitrana, Binary self-adding sequences (64-70);
Gianina Georgescu, The orthogonality of some complexity measures of context-free languages (73-78);
Peter Gvozdjak and Branislav Rovan, Time-bounded parallel rewriting (79-87);
Markus Holzer, On emptiness and counting for alternating finite automata (88-97);
Masami Ito, Height functions and linear languages (98-101). Petr Jancar, Frantisek Mraz, Martin Platek, Martin Prochazka and Jorg Vogel, Restarting automata, Marcus grammars and context-free languages (102-111);
Joanna Jedrzejowicz, An undecidable problem for shuffle languages (112-118);
Lila Kari and Gabriel Thierrin, Morphisms and associated congruences (119-128);
Manfred Kudlek and Alexandru Mateescu, Rational and algebraic languages with distributed catenation (129-138);
Marjo Lipponen, On \(F\)-prime solutions of the Post correspondence problem (139-147);
Codrut Matei and Ferucio Laurentiu Tiplea, \((0,1)\)-total pure context-free grammars (148-153);
Kai Salomaa and Sheng Yu, Nondeterminis m degrees for context-free languages (154-165);
Ina Schiering and Wolfgang Thomas, Counter-free automata, first-order logic, and star-free expressions extended by prefix oracles (166-175);
Andreas Weber, Transforming a single-valued transducer into a Mealy machine (176-185);
Igor Banik, Colonies as systems of Turing machines without states (189-198). Henning Bordihn and Henning Fernau, Accepting grammars and systems: an overview (199-208);
Liming Cai, The computational complexity of PCGS with regular components (209-219);
Rudolf Freund, Array grammar systems with prescribed teams of array productions (220-229);
Stefan Gartner, On partition limited 0L systems (230-236);
Juraj Hromkovic, On the communication complexity of distributive language generation (237-246);
Valeria Mihalache, Szilard languages associated to parallel communicating grammar systems (247-256);
Owen Rambow, Imposing vertical context conditions on derivations (257-266);
Giorgio Satta, The membership problem for unordered vector languages (267-275);
Heiko Dorr, Computing an upper bound for SVS(gg) by abstract interpretation (279-288);
Frank Drewes, On the connectedness of pictures defined by iterated function systems (289-298);
Dora Giammarresi, Finite state recognizability for two-dimensional languages: a brief survey (299-308). Peter Hartmann, Efficient subgraph matching within cellular hypergraphs (309-318);
Yoshimasa Kimura and Takehiro Tokuda, Timed attribute hypergraph grammars and their basic properties (319-328);
Ra lf Stiebe, Some new decision results for edge grammars (329-338);
Hugues Calbrix and Maurice Nivat, Prefix and period languages of rational \(\omega\)-languages (341-349);
Arto Lepistö, On the computational complexity of infinite words (350-359);
Igor Litovsky and Ludwig Staiger, Finite acceptance of infinite words (360-369);
Volker Diekert, Paul Gastin and Antoine Petit, Recent developments in trace theory (373-385);
Manfred Droste and Dietrich Kuske, Trace languages definable with modular quantifiers (386-395);
Ferucio Laurentiu Tiplea and Christian Ene, Hierarchies of Petri net languages and a super-normal form (396-405);
Gianpiero Cattaneo, Enrico Formenti and Giancarlo Mauri, Rule space transformations and one-dimensional cellular automata (409-419). Martin Kutrib and Jorg Richstein, Real-time one-way pushdown cellular automata languages (420-429);
Jiri Sima and Jiri Wiedermann, Neural language acceptors (extended abstract) (430-439);
Peter R. J. Asveld, Towards robustness in parsing—fuzzifying context-free language recognition (443-453);
Blanca Cases, From synonymy to self-modifying automata: Q-Diam language (454-459);
Jose Fortes Galvez, A practical small LR parser with action decision through minimal stack suffix scanning (460-465);
Radu Gramatovici, Introducing the operatorial parser (466-471);
Mark-Jan Nederhof, Reversible pushdown automata and bidirectional parsing (472-481);
Ulrich Nitsche, A finitary-language semantics for propositional linear temporal logic (482-489). The articles of this volume will be reviewed individually.
Indexed articles:
Bercoff, Christiane, A family of \(p\)-uniform tag systems for \(p\)-paperfolding sequences, 3-12 [Zbl 1096.68688]
Berstel, Jean, Recent results in Sturmian words, 13-24 [Zbl 1096.68689]
Cassaigne, Julien, Special factors of sequences with linear subword complexity, 25-34 [Zbl 1096.68690]
Currie, James O.; Shelton, Robert O., Cantor sets and Dejean’s conjecture, 35-43 [Zbl 1096.68691]
Ilie, Lucian, On disjunctivity, ultimate periodicity and ultimate identity of Păun-Salomaa self-reading sequences, 44-53 [Zbl 1096.68692]
Kari, Jarkko; Niemi, Valtteri, Colored Gauss and tangent codes on the torus, 54-63 [Zbl 1096.68659]
Mitrana, Victor, Binary self-adding sequences, 64-70 [Zbl 1096.68693]
Georgescu, Gianina, The orthogonality of some complex measures of context-free languages, 73-78 [Zbl 1096.68654]
Gvozdjak, Peter; Rovan, Branislav, Time-bounded parallel rewriting, 79-87 [Zbl 1096.68644]
Holzer, Markus, On emptiness and counting for alternating finite automata, 88-97 [Zbl 1096.68629]
Ito, Masami, Height functions and linear languages, 98-101 [Zbl 1096.68656]
Jančar, Petr; Mráz, František; Plátek, Martin; Procházka, Martin; Vogel, Jörg, Restarting automata, Marcus grammars and context-free languages, 102-111 [Zbl 1096.68658]
Jȩdrzejowicz, Joanna, An undecidable problem for shuffle languages, 112-118 [Zbl 1096.68657]
Kari, Lila; Thierrin, Gabriel, Morphisms and associated congruences., 119-128 [Zbl 1096.20502]
Kudlek, Manfred; Mateescu, Alexandru, Rational and algebraic languages with distributed catenation, 129-138 [Zbl 1096.68660]
Lipponen, Marjo, On F-prime solutions of the Post correspondence problem, 139-147 [Zbl 1096.68662]
Matei, Codruţ; Ţiplea, Ferucio Larenţiu, \((0,1)\)-total pure context-free grammars, 148-153 [Zbl 1096.68646]
Salomaa, Kai; Yu, Sheng, Nondeterminism degrees for context-free languages, 154-165 [Zbl 1096.68666]
Schiering, Ina; Thomas, Wolfgang, Counter-free automata, first-order logic, and star-free expressions extended by prefix oracles, 166-175 [Zbl 1096.68667]
Weber, Andreas, Transforming a single-valued transducer into a Mealy machine, 176-185 [Zbl 1096.68668]
Baník, Igor, Colonies as systems of Turing machines without states, 189-198 [Zbl 1096.68622]
Bordihn, Henning; Fernau, Henning, Accepting grammars and systems: an overview, 199-208 [Zbl 1096.68639]
Cai, Liming, The computational complexity of PCGS with regular components, 209-219 [Zbl 1096.68640]
Freund, Rudolf, Array grammar systems with prescribed teams of array productions, 220-229 [Zbl 1096.68642]
Gärtner, Stefan, On partition limited 0L systems, 230-236 [Zbl 1096.68643]
Hromkovič, Juraj, On the communication complexity of distributive language generation, 237-246 [Zbl 1096.68630]
Mihalache, Valeria, Szilard languages associated to parallel communicating grammar systems, 247-256 [Zbl 1096.68664]
Rambow, Owen, Imposing vertical context conditions on derivations, 257-266 [Zbl 1096.68647]
Satta, Giorgio, The membership problem for unordered vector languages, 267-275 [Zbl 1096.68631]
Dörr, Heiko, Computing an upper bound for SVS(gg) by abstract interpretation, 279-288 [Zbl 1096.68641]
Drewes, Frank, On the connectedness of pictures defined by iterated function systems, 289-298 [Zbl 1096.68628]
Giammarresi, Dora, Finite state recognizability for two-dimensional languages: a brief survey, 299-308 [Zbl 1096.68655]
Hartmann, Peter, Efficient subgraph matching within cellular hypergraphs, 309-318 [Zbl 1096.68645]
Stiebe, Ralf, Some new decision results for edge grammars, 329-338 [Zbl 1096.68648]
Calbrix, Hugues; Nivat, Maurice, Prefix and period languages of rational \(\omega\)-languages, 341-349 [Zbl 1096.68651]
Lepistö, Arto, On the computational complexity of infinite words, 350-359 [Zbl 1096.68661]
Litovsky, Igor; Staiger, Ludwig, Finite acceptance of infinite words, 360-369 [Zbl 1096.68663]
Diekert, Volker; Gastin, Paul; Petit, Antoine, Recent developments in trace theory, 373-385 [Zbl 1096.68652]
Droste, Manfred; Kuske, Dietrich, Trace languages definable with modular quantifiers, 386-395 [Zbl 1096.68653]
Tiplea, Ferucio Laucenţiu; Ene, Christian, Hierarchies of Petri net languages and a super-normal form, 396-405 [Zbl 1096.68680]
Cattaneo, Gianpiero; Formenti, Enrico; Mauri, Giancarlo, Rule space transformations and one-dimensional cellular automata, 409-419 [Zbl 1096.68675]
Kutrib, Martin; Richstein, Jörg, Real-time one-way pushdown cellular automata languages, 420-429 [Zbl 1096.68676]
Šíma, Jiří; Wiedermann, Jiří, Neural language acceptors. (Extended abstract), 430-439 [Zbl 1096.68649]
Asveld, Peter R. J., Towards robustness in parsing – fuzzifying context-free language recognition, 443-453 [Zbl 1096.68650]
Nitsche, Ulrich, A finitary-language semantics for propositional linear temporal logic, 482-489 [Zbl 1096.68672]

MSC:

00B25	Proceedings of conferences of miscellaneous specific interest
68-06	Proceedings, conferences, collections, etc. pertaining to computer science
94-06	Proceedings, conferences, collections, etc. pertaining to information and communication theory
03-06	Proceedings, conferences, collections, etc. pertaining to mathematical logic and foundations
68Q45	Formal languages and automata
68R15	Combinatorics on words
11B85	Automata sequences

Keywords:

Magdeburg (Germany); Proceedings; Conference; Language theory