Theoretical Computer Science

Inhaltsverzeichnis

• Context-free sets of infinite words.
• New aspects of homomorphisms.
• Can partial correctness assertions specify programming language semantics?.
• An algebraic theory for synchronization.
• Storage modification machines.
• Negative results on counting.
• Strong non-deterministic context-free languages.
• Information content characterizations of complexity theoretic properties.
• Mittlere Anzahl von Rebalancierungsoperationen in gewichtsbalancierten Bäumen.
• A new recursion induction principle.
• Finite-change automata.
• Move rules and trade-offs in the pebble game.
• Transition diagrams and strict deterministic grammars.
• Exact expressions for some randomness tests.
• On storage optimization for automatically generated compilers.
• On continuous completions.
• A new method to show lower bounds for polynomials which are hard to compute.
• On zerotesting-bounded multicounter machines.
• When are two effectively given domains identical?.
• Sur deux langages linéaires.
• An efficient on-line position tree construction algorithm.
• Sorting presorted files.
• Node-visit optimal 1 – 2 brother trees.
• A graph theoretic approach to determinism versus non-determinism.
• Une caracterisation de trois varietes de langages bien connues.
• Über eine minimale universelle Turing-Maschine.
• Sur les varietes de langages et de monoïdes.
• Automaten in planaren graphen.
• Theoreme de transversale rationnelle pour les automates a pile deterministes.
• On the additive complexity of polynomials and some new lower bounds.
• Remarks on the nonexistence of some covering grammars.
• Zur Komplexität der Presburger Arithmetik und des Äquivalenzproblems einfacher Programme.