Turing Machines with Sublogarithmic Space

Pirmais vāks
Springer Science & Business Media, 1994. gada 29. aug. - 114 lappuses
This comprehensive monograph investigates the computational power of Turing machines with sublogarithmic space. The studies are devoted to the Turing machine model introduced by Stearns, Hartmanis, and Lewis (1965) with a two-way read-only input tape and a separate two-way read-write work tape. The book presents the key results on space complexity, also as regards the classes of languages acceptable, under the perspective of a sublogarithmic number of cells used during computation. It originates from courses given by the author at the Technical University of Gdansk and Gdansk University in 1991 and 1992. It was finalized in 1994 when the author visited Paderborn University and includes the most recent contributions to the field.
 

Atlasītās lappuses

Saturs

1 Introduction
1
2 Basic Notions
7
22 Configuration and Computation
9
23 Internal Configuration
11
24 Alternating Turing Machines
12
25 Space Complexity
13
3 Languages Acceptable with Logarithmic Space
15
32 Pebble Automata
16
8 Strong Versus Weak Mode of Space Complexity
61
82 Weak and Strong Complexity Classes above Logarithm
62
83 Weak and Strong Complexity Classes below Logarithm
63
84 Strong Mode of Space Complexity for Recognizing Machines
66
9 Padding
67
92 Padding below Logarithm
70
10 Deterministic Versus Nondeterministic Turing Machines
77
102 Determinism Versus Nondeterminism below Logarithm
78

33 NSPACElog n Complete Language
18
4 Examples of Languages Acceptable with Sublogarithmic Space
21
42 Tally Languages Acceptable with Sublogarithmic Space
24
5 Lower Bounds for Accepting Nonregular Languages
27
51 Lower Bounds for Twoway Turing Machines
28
52 Lower Bounds for Oneway Turing Machines
33
53 Lower Bounds for the Middle Mode of Space Complexity
34
6 Space Constructible Functions
37
62 Fully Space Constructible Functions
39
63 Nondeterministically Fully Space Constructible Functions
42
7 Halting Property and Closure under Complement
47
71 Halting Property of Turing Machines with Logarithmic or Greater Space
48
72 Closure under Complement of Strong Deterministic Complexity Classes
49
Nondeterministic Space Complexity Classes above Logarithm
52
74 Closure under Complement for Bounded Languages Acceptable by Nondeterministic Turing Machines
53
75 Nonclosure under Complement of Language Acceptable by Weakly Spacebounded Turing Machines
55
11 Space Hierarchy
81
112 Space Hierarchy below Logarithm
82
12 Closure under Concatenation
85
13 Alternating Hierarchy
89
131 Collapsing of the Alternating Hierarchy above Logarithm
90
132 Noncollapsing of the Alternating Hierarchy below Logarithm
92
14 Independent Complement
95
15 Other Models of Turing Machines
99
151 Twodimensional Turing Machines
100
152 Inkdot Turing Machines
104
153 1pebble Turing Machines
107
154 Demon Turing Machines
109
References
111
Subject Index
113
Symbol Index
Autortiesības

Citi izdevumi - Skatīt visu

Turing Machines with Sublogarithmic Space
Andrzej Szepietowski
Fragmentu skats - 1994
Turing Machines with Sublogarithmic Space
Andrzej Szepietowski
Priekšskatījums nav pieejams - 2014
Turing Machines with Sublogarithmic Space
Andrzej Szepietowski
Priekšskatījums nav pieejams - 2006

Bieži izmantoti vārdi un frāzes

1-inkdot Turing machine 1-pebble Turing machine 2-space accepting configuration accepting non-regular languages akbm alternating hierarchy alternating Turing machine am+km arbitrary binary bound for accepting cell closed under complement configuration ẞ constant denotes deterministic or nondeterministic deterministic Turing machine DSPACE DSPACE[log existential finite fully space constructible function L(n Hence Hopcroft and Ullman initial configuration input of length input tape L₁(n language LOG languages accepted least common multiple Lemma Li(n lim inf log log n log n space log n space-bounded log-space reducible logn and L(n loops lower bound M₁ M₂ mode of space nondeterministic Turing machine NSPACE[L(n O(log log padding argument pebble proof of Theorem prove push-down tape reaches recognizing Turing machine regular language simulated space complexity classes space constructible functions space-bounded deterministic Turing space-bounded internal configurations space-bounded nondeterministic Turing space-bounded Turing machine strong mode strong-NSPACE[L(n strongly L(n sublogarithmic space symbol Szepietowski weak-DSPACE[log log

Atsauces uz šo grāmatu

Bibliogrāfiskā informācija

NosaukumsTuring Machines with Sublogarithmic Space
Grāmatas Lecture Notes in Computer Science 843. sējums. sējums
AutorsAndrzej Szepietowski
RedaktorsAndrzej Szepietowski
Izdevums:ilustrēts
IzdevējsSpringer Science & Business Media, 1994
ISBN3540583556, 9783540583554
Apjoms114 lappuses
  
Eksportēt avotuBiBTeX EndNote RefMan