Automata, Languages, and Programming

Inhaltsverzeichnis

• Sharing in nondeterminism.
• Sur les mots sans carré définis par un morphisme.
• A characterization of abstract data as model-theoretic invariants.
• Inherent ambiguities in families of grammars extended abstract.
• Representing complexity classes by equality sets.
• Supercounter machines.
• Existential quantifiers in abstract data types.
• A generalization of Ginsburg and Rose's characterization of G-S-M mappings.
• Strict deterministic languages and controlled rewriting systems.
• A string matching algorithm fast on the average.
• Functional characterization of some semantic equalities inside ?-calculus.
• Arbitration and queueing under limited shared storage requirements.
• On the homomorphic characterizations of families of languages.
• Two level grammars: CF-grammars with equation schemes.
• Proving termination with multiset orderings.
• One abstract accepting algorithm for all kinds of parsers.
• Studies in abstract/concrete mappings in proving algorithm correctness.
• A characterization of a dot-depth two analogue of generalized definite languages.
• Partitioned LL(k) grammars.
• Recursion schemes and generalized interpretations.
• A rational theory of AFLs.
• On the succinctness of different representations of languages.
• A fixed-point theorem for recursive-enumerable languages and some considerations about fixed-point semantics of monadic programs.
• Hierarchic index sequential search with optimal variable block size and its minimal expected number of comparisons.
• A unique termination theorem for a theory with generalised commutative axioms.
• Dags and Chomsky hierarchy.
• Recent advances in the probabilistic analysis of graph-theoretic algorithms.
• On the average stack size of regularly distributed binary trees.
• On reductions of parallel programs.
• On the height of derivationtrees.
• The modal logic of programs.
• A comparison between two variations of a pebble game on graphs.
• LL(k) parsing for attributed grammars.
• On eliminating nondeterminism from Turing machines which use less than logarithm worktape space.
• Structure preserving transformations on non-left-recursive grammars.
• The complexity of restricted minimum spanning tree problems.
• A systematic approach to formal language theory through parallel rewriting.
• Extending the notion of finite index.
• On the complexity of general context-free language parsing and recognition.
• Space-time tradeoffs for oblivious integer multiplication.
• Investigating programs in terms of partial graphs.
• On the power of random access machines.
• An axiomatic treatment of ALGOL 68 routines.
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP.
• Constructing call-by-value continuation semantics.
• A formal semantics for concurrent systems.
• On constructing LL(k) parsers.
• More on advice on structuring compilers and proving them correct.
• Languages of nilpotent and solvable groups (extended abstract).
• Unique fixed points vs. least fixed points.
• A modification of the LR(k) method for constructing compact bottom-up parsers.
• Optimal decomposition of linear automata.
• Bracketed two-level grammars — A decidable and practical approach to language definitions.