QUANTIFYING THE AMOUNT OF VERBOSENESS

Authors
BEIGEL R KUMMER M STEPHAN F
Citation
R. Beigel et al., QUANTIFYING THE AMOUNT OF VERBOSENESS, Information and computation, 118(1), 1995, pp. 73-90
Citations number
42
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
118
Issue
1
Year of publication
1995
Pages
73 - 90
Database
ISI
SICI code
0890-5401(1995)118:1<73:QTAOV>2.0.ZU;2-G
Abstract
We study the fine structure of the classification of sets of natural n umbers A according to the number of queries which are needed to comput e the n-fold characteristic function of A. A complete characterization is obtained, relating the question to finite combinatorics. In order to obtain an explicit description we consider several interesting comb inatorial problems. (C) 1995 Academic Press, Inc.