Automata, Languages, and Programming

Inhaltsverzeichnis

• The theory of data dependencies — An overview.
• The VLSI revolution in theoretical circles.
• Tuple sequences and indexes.
• The complexity of cubical graphs.
• P-generic sets.
• Functional dependencies and disjunctive existence constraints in database relations with null values.
• The algebra of recursively defined processes and the algebra of regular processes.
• Algebraic specification of exception handling and error recovery by means of declarations and equations.
• Building the minimal DFA for the set of all subwords of a word on-line in linear time.
• The complexity and decidability of separation.
• Concurrent transmissions in broadcast networks.
• Linear searching for a square in a word.
• Domain algebras.
• Principality results about some matrix languages families.
• Oriented equational clauses as a programming language.
• Relational algebra operations and sizes of relations.
• Some results about finite and infinite behaviours of a pushdown automaton.
• On the relationship of CCS and petri nets.
• Communicating finite state machines with priority channels.
• A modal characterization of observational congruence on finite terms of CCS.
• Communication complexity.
• Space and time efficient simulations and characterizations of some restricted classes of PDAS.
• A complete axiom system for algebra of closed-regular expression.
• The complexity of finding minimum-length generator sequences.
• On probabilistic tape complexity and fast circuits for matrix inversion problems.
• On three-element codes.
• Recursion depth analysis for special tree traversal algorithms.
• Performance analysis of Shamir's attack on the basic Merkle-Hellman knapsack cryptosystem.
• Measures of presortedness and optimal sorting algorithms.
• Languages and inverse semigroups.
• Area-time optimal vlsi integer multiplierwith minimum computation time.
• On the interpretation of infinite computations in logic programming.
• A linear time algorithm to solve the single function coarsest partition problem.
• Complexité des facteurs des mots infinis engendrés par morphismes itérés.
• Automates boustrophedon, semi-groupe de birget et monoide inversif libre.
• Probabilistic bidding gives optimal distributed resource allocation.
• Partial order semantics versus interleaving semantics for CSP — like languages and its impact on fairness.
• Cancellation, pumping and permutation in formal languages.
• A hardware implementation of the CSP primitives and its verification.
• Factorization of univariate integer polynomials by diophantine approximation and an improved basis reduction algorithm.
• Robust algorithms: A different approach to oracles.
• Node weighted matching.
• The propositional mu-calculus is elementary.
• AVL-trees for localized search.
• The simple roots of real-time computation hierarchies.
• Computational complexity of an optical disk interface.
• Encoding graphs by derivations and implications for the theory of graph grammars.
• Sampling algorithms for differential batch retrieval problems (extended abstract).