Resource-bounded strong dimension versus resource-bounded category

被引：2
|
作者：
Hitchcock, JM
Pavan, A
机构：
[1] Univ Wyoming, Dept Comp Sci, Laramie, WY 82071 USA
[2] Iowa State Univ Sci & Technol, Dept Comp Sci, Ames, IA 50011 USA
来源：
INFORMATION PROCESSING LETTERS | 2005年 / 95卷 / 03期
基金：
美国国家科学基金会;
关键词：
computational complexity; resource-bounded category; resource-bounded dimension; resource-bounded measure;
D O I：
10.1016/j.ipl.2005.05.001
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Classically it is known that any set with packing dimension less than 1 is meager in the sense of Baire category. We establish a resource-bounded extension: if a class X has A-strong dimension less than 1, then X is Delta-meager. This has the applications of explaining some of Lutz's simultaneous Delta-meager, Delta-measure 0 results and providing a new proof of a Gu's strong dimension result on infinitely-often classes. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：377 / 381
页数：5
相关论文
共 50 条
  • [1] On the Complexity of Resource-Bounded Logics
    Alechina, Natasha
    Bulling, Nils
    Demri, Stephane
    Logan, Brian
    REACHABILITY PROBLEMS, RP 2016, 2016, 9899 : 36 - 50
  • [2] Resource-bounded measure and learnability
    Lindner, W
    Schuler, R
    Watanabe, O
    THEORY OF COMPUTING SYSTEMS, 2000, 33 (02) : 151 - 170
  • [3] On pseudorandomness and resource-bounded measure
    Arvind, V
    Köbler, J
    THEORETICAL COMPUTER SCIENCE, 2001, 255 (1-2) : 205 - 221
  • [4] Resource-bounded fraud detection
    Torgo, Luis
    PROGRESS IN ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2007, 4874 : 449 - 460
  • [5] On the complexity of resource-bounded logics
    Alechina, N.
    Bulling, N.
    Demri, S.
    Logan, B.
    THEORETICAL COMPUTER SCIENCE, 2018, 750 : 69 - 100
  • [6] Resource-bounded reasoning and paraconsistency
    Allen, M
    Jennings, RE
    IC-AI'2001: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOLS I-III, 2001, : 796 - 802
  • [7] Resource-bounded paraconsistent inference
    Marquis, P
    Porquet, N
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2003, 39 (04) : 349 - 384
  • [8] Results on resource-bounded measure
    Buhrman, H
    Fenner, S
    Fortnow, L
    AUTOMATA, LANGUAGES AND PROGRAMMING, 1997, 1256 : 188 - 194
  • [9] Resource-Bounded Measure and Learnability
    W. Lindner
    R. Schuler
    O. Watanabe
    Theory of Computing Systems, 2000, 33 : 151 - 170
  • [10] On resource-bounded instance complexity
    Fortnow, L
    Kummer, M
    THEORETICAL COMPUTER SCIENCE, 1996, 161 (1-2) : 123 - 140
12345