Automata, Languages and Programming: Sixth Colloquium, Graz, Austria, July 16–20, 1979 [1 ed.] 9783540095101, 3540095101 [DJVU]

Table of contents :
Sharing in nondeterminism....Pages 1-15
Sur les mots sans carré définis par un morphisme....Pages 16-25
A characterization of abstract data as model-theoretic invariants....Pages 26-37
Inherent ambiguities in families of grammars extended abstract....Pages 38-48
Representing complexity classes by equality sets....Pages 49-57
Supercounter machines....Pages 58-72
Existential quantifiers in abstract data types....Pages 73-87
A generalization of Ginsburg and Rose's characterization of G-S-M mappings....Pages 88-103
Strict deterministic languages and controlled rewriting systems....Pages 104-117
A string matching algorithm fast on the average....Pages 118-132
Functional characterization of some semantic equalities inside λ-calculus....Pages 133-146
Arbitration and queueing under limited shared storage requirements....Pages 147-160
On the homomorphic characterizations of families of languages....Pages 161-170
Two level grammars: CF-grammars with equation schemes....Pages 171-187
Proving termination with multiset orderings....Pages 188-202
One abstract accepting algorithm for all kinds of parsers....Pages 203-217
Studies in abstract/concrete mappings in proving algorithm correctness....Pages 218-229
A characterization of a dot-depth two analogue of generalized definite languages....Pages 230-244
Partitioned LL(k) grammars....Pages 245-255
Recursion schemes and generalized interpretations....Pages 256-270
A rational theory of AFLs....Pages 271-281
On the succinctness of different representations of languages....Pages 282-288
A fixed-point theorem for recursive-enumerable languages and some considerations about fixed-point semantics of monadic programs....Pages 289-303
Hierarchic index sequential search with optimal variable block size and its minimal expected number of comparisons....Pages 304-315
A unique termination theorem for a theory with generalised commutative axioms....Pages 316-330
Dags and Chomsky hierarchy....Pages 331-337
Recent advances in the probabilistic analysis of graph-theoretic algorithms....Pages 338-339
On the average stack size of regularly distributed binary trees....Pages 340-355
On reductions of parallel programs....Pages 356-369
On the height of derivation trees....Pages 370-384
The modal logic of programs....Pages 385-409
A comparison between two variations of a pebble game on graphs....Pages 411-421
LL(k) parsing for attributed grammars....Pages 422-430
On eliminating nondeterminism from Turing machines which use less than logarithm worktape space....Pages 431-445
Structure preserving transformations on non-left-recursive grammars....Pages 446-459
The complexity of restricted minimum spanning tree problems....Pages 460-470
A systematic approach to formal language theory through parallel rewriting....Pages 471-478
Extending the notion of finite index....Pages 479-488
On the complexity of general context-free language parsing and recognition....Pages 489-497
Space-time tradeoffs for oblivious integer multiplication....Pages 498-504
Investigating programs in terms of partial graphs....Pages 505-519
On the power of random access machines....Pages 520-529
An axiomatic treatment of ALGOL 68 routines....Pages 530-545
P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP....Pages 546-555
Constructing call-by-value continuation semantics....Pages 556-570
A formal semantics for concurrent systems....Pages 571-584
On constructing LL(k) parsers....Pages 585-595
More on advice on structuring compilers and proving them correct....Pages 596-615
Languages of nilpotent and solvable groups (extended abstract)....Pages 616-632
Unique fixed points vs. least fixed points....Pages 633-645
A modification of the LR(k) method for constructing compact bottom-up parsers....Pages 646-658
Optimal decomposition of linear automata....Pages 659-667
Bracketed two-level grammars — A decidable and practical approach to language definitions....Pages 668-682