Automata, Languages and Programming

O. Kariv

ISBN 10: 3540108432 / ISBN 13: 9783540108436

Editore: Springer Berlin Heidelberg, Springer Berlin Heidelberg Jun 1981, 1981

Riguardo questo articolo

This item is printed on demand - it takes 3-4 days longer - Neuware -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 n¿ 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. 564 pp. Englisch.

Codice articolo 9783540108436

Dati bibliografici

• Titolo: Automata, Languages and Programming
• Editore: Springer Berlin Heidelberg, Springer Berlin Heidelberg Jun 1981
• Data di pubblicazione: 1981
• Lingua: Inglese
• ISBN 10: 3540108432
• ISBN 13: 9783540108436
• Rilegatura: Taschenbuch
• Condizione: Neu
• Dimensioni: 235 L x 155 A x 31 P (millimetri) 235 millimetri di larghezza per 155 millimetri di altezza per 31 millimetri di profondità
• Peso: 844 grammi

Descrizione articolo

Contenuti

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 n×n 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.