Titlebook: Mathematical Foundations of Computer Science 1992; 17th International S Ivan M. Havel,Václav Koubek Conference proceedings 1992 Springer-Ve

Petechiae

Some remarks on the test complexity of iterative logic arrays,onsidered. We prove that the . of such an ILA is either constant or linear in the length of the ILA. The determination of the test complexity and the specification of the test set can be carried out by algorithms whose complexity only depends on the individual cell function of the ILA. . which chara

Silent-Ischemia

The degree structure of 1-L reductions,mplete sets for PSPACE that are not 1-L isomorphic. In other words, the 1-L complete degree for PSPACE does not collapse. This contrasts a result of Allender who showed that all 1-L complete sets for PSPACE are polynomial-time isomorphic. Since all 1-L complete sets for PSPACE are equivalent under 1

debris

Serenity

Rational transductions and complexity of counting problems,r and context-free languages. This approach allows to obtain old and new results on the complexity of ranking and unranking as well as on other problems concerning the number of prefixes, suffixes, subwords and factors of a word which belong to a fixed language. Other results concern a suboptimal co

叙述

出处

Anecdote

Anthrp

DIKE

Graph layout problems,In this paper we survey the recent results and open questions about some graph layout problems.

搜集

Neural networks and complexity theory,We survey some of the central results in the complexity theory of neural networks, with pointers to the literature.