Fundamentals of Computation Theory

Inhaltsverzeichnis

• 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.