Automata, Languages and Programming

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 49 Characterizations of PUNC and precomputation
3. Altmetric Badge
   Chapter 50 Comparison of algorithms controlling concurrent access to a database: A combinatorial approach
4. Altmetric Badge
   Chapter 51 A new duality result concerning Voronoi diagrams
5. Altmetric Badge
   Chapter 52 Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial
6. Altmetric Badge
   Chapter 53 On exponential lowness
7. Altmetric Badge
   Chapter 54 A tradeoff between search and update time for the implicit dictionary problem
8. Altmetric Badge
   Chapter 55 Intersections of some families of languages
9. Altmetric Badge
   Chapter 56 Correspondence between ternary simulation and binary race analysis in gate networks
10. Altmetric Badge
    Chapter 57 Counting with rational functions
11. Altmetric Badge
    Chapter 58 Finite biprefix sets of paths in a Graph
12. Altmetric Badge
    Chapter 59 Parallel RAMs with owned global memory and deterministic context-free language recognition
13. Altmetric Badge
    Chapter 60 A Strong restriction of the inductive completion procedure
14. Altmetric Badge
    Chapter 61 On discerning words by automata
15. Altmetric Badge
    Chapter 62 Complexity classes without machines: On complete languages for UP
16. Altmetric Badge
    Chapter 63 Containment, separation, complete sets, and immunity of complexity classes
17. Altmetric Badge
    Chapter 64 On nontermination of Knuth-Bendix algorithm
18. Altmetric Badge
    Chapter 65 Tradeoffs for language recognition on parallel computing models
19. Altmetric Badge
    Chapter 66 Rational equivalence relations
20. Altmetric Badge
    Chapter 67 Some further results on digital search trees
21. Altmetric Badge
    Chapter 68 Knowledge, belief and time
22. Altmetric Badge
    Chapter 69 A termination detector for static and dynamic distributed systems with asynchronous non-first-in-first-out communication
23. Altmetric Badge
    Chapter 70 Decompositions of nondeterministic reductions
24. Altmetric Badge
    Chapter 71 Hierarchical planarity testing algorithms
25. Altmetric Badge
    Chapter 72 Synthesis and equivalence of concurrent systems
26. Altmetric Badge
    Chapter 73 The set union problem with backtracking
27. Altmetric Badge
    Chapter 74 Torsion matrix semigroups and recognizable transductions
28. Altmetric Badge
    Chapter 75 On recognizable subsets of free partially commutative monoids
29. Altmetric Badge
    Chapter 76 Min Cut is NP-complete for edge weighted trees
30. Altmetric Badge
    Chapter 77 Alternating automata, the weak monadic theory of the tree, and its complexity
31. Altmetric Badge
    Chapter 78 Subpolynomial complexity classes of real functions and real numbers
32. Altmetric Badge
    Chapter 79 Etude syntaxique des parties reconnaissables de mots infinis
33. Altmetric Badge
    Chapter 80 Refusal testing
34. Altmetric Badge
    Chapter 81 A timed model for communicating sequential processes
35. Altmetric Badge
    Chapter 82 A uniform reduction theorem extending a result of J. Grollmann and A. Selman
36. Altmetric Badge
    Chapter 83 On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
37. Altmetric Badge
    Chapter 84 A new approach to detection of locally indicative stability
38. Altmetric Badge
    Chapter 85 A more efficient algorithm for lattice basis reduction
39. Altmetric Badge
    Chapter 86 Lower bounds by recursion theoretic arguments
40. Altmetric Badge
    Chapter 87 An improved algorithm for transitive closure on acyclic digraphs
41. Altmetric Badge
    Chapter 88 Un algorithme determinant les melanges de deux mots
42. Altmetric Badge
    Chapter 89 A very fast, practical algorithm for finding a negative cycle in a digraph
43. Altmetric Badge
    Chapter 90 A compositional reformulation of Owicki-Gries's partial correctness logic for a concurrent while language
44. Altmetric Badge
    Chapter 91 Semigroups and languages of dot-depth 2
45. Altmetric Badge
    Chapter 92 A parallel vertex insertion algorithm for minimum spanning trees
46. Altmetric Badge
    Chapter 93 More complicated questions about maxima and minima, and some closures of NP
47. Altmetric Badge
    Chapter 94 Lower bounds for dynamic range query problems that permit subtraction (extended abstract)
48. Altmetric Badge
    Chapter 95 E-unification algorithms for a class of confluent term rewriting systems
49. Altmetric Badge
    Chapter 96 On fixed-point clones