Fundamentals of Computation Theory de Lothar Budach

Fundamentals of Computation Theory

Lothar Budach

This volume contains papers which were contributed forpresentation at the international conference "Fundamentalsof Computation Theory - FCT '91" heldat Gosen, near Berlin,September 9-13, 1991. This was the eighth in the series ofFCT conferences organized every odd year. The programme oftheconference, including invited lectures and selectedcontributions, falls into the following categories:- Semantics and logical concepts in the theory of computing,formal specification,- Automata and formal languages, Computational geometry,- Algorithmic aspects of algebra and algebraic geometry,cryptography,- Complexity (sequential, parallel, distributedcomputing, structure, lower bounds, complexity of analyticalproblems, general concepts),- Algorithms (efficient, probabilistic, parallel,sequential, distributed),- Counting and combinatorics in connection with mathematicalcomputer science.The proceedings of previous FCT meetings are available asLecture Notes in Computer Science (Vols. 380, 278, 199, 158,117, 56).

Citește tot Restrânge

	Preț	Express
Paperback (2)	326^.87 lei 6-8 săpt.
Springer Berlin, Heidelberg – 28 aug 1991	326^.87 lei 6-8 săpt.
Springer – aug 1985	416^.69 lei 6-8 săpt.

Preț

Express

Paperback (2)

326^.87 lei 6-8 săpt.

Springer Berlin, Heidelberg – 28 aug 1991

326^.87 lei 6-8 săpt.

Springer – aug 1985

416^.69 lei 6-8 săpt.

Cuprins

Space complexity of alternating Turing machines.- A unifying theorem for algebraic semantics and dynamic logics.- On some "non-uniform" complexity measures.- Fast parallel vertex colouring.- Muller automata and bi-infinite words.- On formal languages, probabilities, paging and decoding algorithms.- On the restriction of some NP-complete graph problems to permutation graphs.- Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic.- Algorithms solving path systems.- Decidability of confluence for ground term rewriting systems.- Lower bounds on the complexity of 1-time only branching programs (Preliminary version).- On coordinated rewriting.- Elements of a general theory of combinatorial structures.- A language theoretic approach to serialization problem in concurrent systems.- Logic programming and substitutions.- A lower bound on the oscilation complexity of context-free languages.- Depth efficient transformations of arithmetic into boolean circuits.- Free cost measures of trees.- Discrete extremal problems on covering.- Parallel algorithms for connected components in a graph.- Statistical testing of finite sequences based on algorithmic complexity.- Lower bounds for boolean formulae of depth 3 and the topology of the n-Cube (Preliminary version).- Clustering to minimize the sum of volumes of convex hulls of clusters is NP-complete.- Linear comparison complexity of the n-cube membership problem.- String grammars with disconnecting.- Array processing machines.- A fast heuristic for covering polygons by rectangles.- ? ??????? ? ???????????? ?????? ????????? ??????.- Products of group languages.- The complexity of embedding graphs into binary trees.- On some topological properties of logicprograms.- Recent results on continuous ordered algebras.- Are lower bounds on the complexity lower bounds for universal circuits?.- Probabilistic algorithms in group theory.- Recent results on codes.- A multiparameter analysis of the boundedness problem for vector addition systems.- About two-way transducers.- Parallel time O(log N) recognition of unambiguous CFLs.- On colour critical graphs.- Generalized thue-morse sequences.- Tree-partite graphs and the complexity of algorithms.- A quadratic regularity test for non-deleting macro s grammars.- Continuous abstract data types: Basic machinery and results.- On the length of single dynamic tests for monotone boolean functions.- Enumerative combinatorics and algebraic languages.- On several kinds of space-bounded on-line multicounter automata.- Iterated linear control and iterated one-turn pushdowns.- On the boolean closure of NP.- The critical complexity of all (monotone) boolean functions and monotone graph properties.- Degeneration of Shimura surfaces and a problem in coding theory.- Quantifiers in combinatory PDL: Completeness, definability, incompleteness.- Partial ordering derivations for CCS.- Intersecting two polyhedra one of which is convex.