Author name cluster

Andreas Klein

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

I&C Journal 2007 Journal Article

Extended visual cryptography schemes

Andreas Klein
Markus Wessler

Visual cryptography schemes have been introduced in 1994 by Naor and Shamir. Their idea was to encode a secret image into n shadow images and to give exactly one such shadow image to each member of a group P of n persons. Whereas most work in recent years has been done concerning the problem of qualified and forbidden subsets of P or the question of contrast optimizing, in this paper we study extended visual cryptography schemes, i. e. , shared secret systems where any subset of P shares its own secret.

Details DOI

TCS Journal 2003 Journal Article

Fast one-way cellular automata

Andreas Klein
Martin Kutrib

Space-bounded one-way cellular language acceptors (OCA) are investigated. The only inclusion known to be strict in their time hierarchy from real-time to exponential-time is between real-time and linear-time! We show the surprising result that there exists an infinite hierarchy of properly included OCA-language families in that range. A generalization of a method in Terrier (Theoret. Comput. Sci. 156 (1–2) (1996) 281) is shown which provides a tool for proving that languages are not acceptable by OCAs with small time bounds. The hierarchies are established by such a language and a translation result. In addition, a notion of constructibility for CAs is introduced, along with some of its properties. We prove several closure properties of the families in the hierarchy.

Details DOI

TCS Journal 2002 Journal Article

Deterministic Turing machines in the range between real-time and linear-time

Andreas Klein
Martin Kutrib

Deterministic k-tape and multitape Turing machines with one-way, two-way and without a separated input tape are considered. We investigate the classes of languages acceptable by such devices with time bounds of the form n+r(n), where r∈ o(n) is a sublinear function. It is shown that there exist infinite time hierarchies of separated complexity classes in that range. For these classes weak closure properties are proved.

Details DOI