Fundamentals of Computation Theory: 9th International Conference, FCT '93, Szeged, Hungary, August 23-27, 1993. Proceedings: 710 - Brossura

Esik, Zoltan

Brossura

ISBN 10: 3540571639 ISBN 13: 9783540571636

Casa editrice: Springer, 2008

Riassunto

This volume contains the proceedings of the Ninth Conferenceon Fundamentalsof Computation Theory (FCT 93) held inSzeged, Hungary, in August 1993. The conference was devotedto a broad range of topics including:- Semanticsand logical concepts in the theory of computingand formal specification- Automata and formal languages- Computational geometry, algorithmic aspects of algebra andalgebraic geometry, cryptography- Complexity (sequential, parallel, distributed computing,structure, lower bounds, complexity of analytical problems,general concepts)- Algorithms (efficient, probabilistic, parallel,sequential, distributed)- Counting and combinatorics in connection with mathematicalcomputer scienceThe volume contains the texts of 8 invitedlectures and 32short communications selected by the international programcommittee from a large number of submitted papers.

Su questo libro

Contenuti

Rewriting, möbius functions and semi-commutations.- Simulations between different models of parallel computers.- Dense and disjunctive properties of languages.- The hierarchy of codes.- Five facets of hyperedge replacement beyond context-freeness.- An action structure for synchronous ?-calculus.- AC0 circuit complexity.- Pattern languages: Problems of decidability and generation.- General solution of mirror equation.- Decidability of equivalence for linear letter to letter top-down tree transducers.- Translations between flowchart schemes and process graphs.- Local equational logic.- Liveness of weighted circuits and the diophantine problem of Frobenius.- Context-free graph grammars: Separating vertex replacement from hyperedge replacement.- Formal languages consisting of primitive words.- Undecidability of the surjectivity problem for 2D cellular automata: A simplified proof.- Efficient interpretation of state charts.- Implementation of a universal unification algorithm for macro tree transducers.- Finding maximum convex polygons.- Approximations with axis-aligned rectangles (extended abstract).- Vector sequence analysis and full weak safety for concurrent systems.- Does transitivity help? On the complexity of poset properties.- Generalized topological sorting in linear time.- Easily checked self-reducibility.- On the complexities of linear LL(1) and LR(1) grammars.- On the relation between firing sequences and processes of Petri nets.- Maximum covering with D cliques.- Monotonically labelled ordered trees and multidimensional binary trees.- A maximum path length pumping lemma for edge-replacement languages.- Regular approximations to shuffle products of context-free languages, and convergence of their generating functions.- The equational theory of a Boolean monad.- Non erasing Taring machines: a frontier between a decidable halting problem and Universality.- On scattered syntactic monoids.- Regular tree languages without unary symbols are star-free.- One-way cellular automata on cayley graphs.- ON tree pattern unification problems.- Structural Equivalence and ETOL grammars.- A hierarchy of deterministic top-down tree transformations.- Synthesis of O(lg n) testable trees.- On the learnability of a restricted predicate formulae.

Dettagli dell?edizione

• Editore: Springer
• Data di pubblicazione: 2008
• Lingua: Inglese
• ISBN 10: 3540571639
• ISBN 13: 9783540571636
• Rilegatura: Copertina flessibile
• Numero di pagine: 488
• Contatto del produttore: non disponibile
• Persona responsabile: CMN Printpool Inh. Mathis Neumann; https://www.also.com/ec/cms5/en_6000/6000/index.jsp; ; Friedrich-Karl-Str. 9; Hamburg; Germania