Titlebook: STACS 88; 5th Annual Symposium Robert Cori,Martin Wirsing Conference proceedings 1988 Springer-Verlag Berlin Heidelberg 1988 Algorithms.Aut

BRINK

Functional equations for data structures,theory of . which has been introduced as a conceptual framework for enumerative combinatorics. The generating functions associated to these abstract data structures are directly derived from the corresponding functional equations.

小淡水鱼

证明无罪

Collapsing oracle hierarchies, census functions and logarithmically many queries,roves in different respects earlier such collapse results in [3], [4] and [13]. Our results on space hierarchy classes have been improved since the first version of this paper by Immerman [8] who showed a collapse to level Σ..

Cholecystokinin

Domino games with an application to the complexity of boolean algebras with bounded quantifier altef deterministic and nondeterministic Turing machines. The domino games are two person games in the course of which the players build up domino-tilings of a square of prescribed size. Acceptance of an alternating Turing machine corresponds to a winning strategy for one player — the number of moves in

Handedness

An automatic speed-up of random access machines with powerful arithmetic instructions,erably lower than the time sequentially used. Here we consider sequential and parallel random access machines (RAMs, PRAMs) with arithmetic instructions {+, −, *}. RAMs work on integer inputs and use direct and a restricted form of indirect addressing, only..We extend the result of . ([MEYE86]) to R

scoliosis

Characterizing the polynomial Hierarchy by alternating auxiliary pushdown automata,le keeping a polynomial time bound. Although recently it was proven by Borodin et al. that the class of languages accepted by nondeterministic logarithmic space bounded auxiliary pushdown automata with a polynomial time bound is closed under complement [Bo et al], it is shown that, surprisingly, the

无思维能力

Hotz-isomorphism theorems in formal language theory,. The main result of the paper states that L is a language with a Hotz-isomorphism if and only if F(X)/L is a finitely presentable group. We also prove an analogous result for Hotz-monoids. Further, we show when the construction of a grammar which allows the Hotz-isomorphism is effective; and we pro

吃掉

First-order properties of trees, star-free expressions, and aperiodicity,t-order definability is strictly weaker than aperiodicity. These two theorems show how far the results of McNaughton and Schützenberger on starfree sets of words (stating the equivalence between first-order definability, star-freeness, and aperiodicity) are transferable to the context of trees. Both

表示向下

probate