Automata, languages and programming : eighth colloquium, Acre (Akko), Israel, July 13-17, 1981

edited by S. Even and O. Kariv


  • Refined analysis and improvements on some factoring algorithms.- Absolute primality of polynomials is decidable in random polynomial time in the number of variables.- Area-time optimal VLSI networks for computing integer multiplication and Discrete Dourier Transform.- Cost tradeoffs in graph embeddings, with applications.- Minimum s-t cut of a planar undirected network in o(n log2(n)) time.- On the density of color-families.- The implication problem for data dependencies.- Characterizing data base Dependencies.- Data flow analysis of applicative programs.- Flow analysis of lambda expressions.- Algorithmic specifications of abstract data types.- Nondeterminism in abstract data types.- A view of directions in relational database theory.- A new characterization of the regular languages.- Langages Reconnaissables et Codage Prefixe Pur.- Passes, sweeps and visits.- On LALR(k) testing.- On size bounds for deterministic parsers.- A decision procedure for the equivalence of two dpdas one of which is linear.- The deducibility problem in Propositional Dynamic Logic.- Finite models for deterministic propositional dynamic logic.- Impartiality, justice and fairness: The ethics of concurrent termination.- Computing a perfect strategy for nxn chess requires time exponential in n.- On the complexity of simple arithmetic expressions.- Proving lower bounds for linear decision trees.- Parikh-bounded languages.- Generalized Parikh mappings and homomorphisms.- Chomsky-Schotzenberger representations for families of languages and grammatical types.- Algebraically specified programming systems and Hoare's logic.- Automatic construction of verification condition generators from hoare logics.- Circular expressions: Elimination of static environments.- An axiomatic approach to the Korenjak - Hopcroft algorithms.- On the (generalized) post correspondence problem with lists of length 2.- A sparse table implementation of priority queues.- Comparing and putting together recursive path ordering, simplification orderings and Non-Ascending Property for termination proofs of term rewriting systems.- Termination of linear rewriting systems.- Realizing an equational specification.- A cook's tour of countable nondeterminism.- The complexity of decision problems for finite-turn multicounter machines.- Alternating multihead finite automata.- The solution for the branching factor of the alpha-beta pruning algorithm.- Uniform complexity and digital signatures.- On the generation of cryptographically strong pseudo-random sequences.- Measuring the expressive power of dynamic logics: An application of abstract model theory.

「Nielsen BookData」より


書名 Automata, languages and programming : eighth colloquium, Acre (Akko), Israel, July 13-17, 1981
著作者等 European Association for Theoretical Computer Science
Even, Shimon
International Colloquium on Automata, Languages and Programming
Kariv, Oded
Kariv O.
Even S.
書名別名 ICALP 81
シリーズ名 Lecture notes in computer science
出版元 Springer-Verlag
刊行年月 1981
ページ数 viii, 550 p.
大きさ 25 cm
ISBN 0387108432
NCID BA01338640
※クリックでCiNii Booksを表示
言語 フランス語
出版国 ドイツ