|  |, (see cardinality of set; length of string) |
| ×, (see Cartesian product) |
  (ceiling function), 301 |
| Ĝ,
(see empty set) |
 , (see empty string) |
| ˘ / $, (see endmarker) |
 *, +, 3 |
| |
| acceptance problem, 36 |
| accepting computation / configuration / state, (see computation / configuration / state,
accepting) |
| acyclic graph, 301 |
| Adleman, L., 298, 302 |
| Aho, A., 89, 267, 302 |
| algorithm, 33 |
| Allender,
E., 298, 302 |
| alphabet, 2 - 4 |
| | binary, 2 |
| | unary, 2 |
| alphabetically |
| | bigger / smaller, 3 |
| | ordered,
4 |
| ambiguity problem, 36, 37, 197, 198 |
| AND gate, 275 |
| assertion, (see predicate) |
| assignment
instruction, (see deterministic assignment instruction; nondeterministic assignment instruction;
random assignment instruction) |
| auxiliary work-tape, 145 |
| | alphabet / symbol, 146 |
| | head,
145 |
| |
| bandwidth problem, 243 |
| Bar-Hillel, Y., 90, 143, 198, 302 |
| Batcher, K., 297, 302 |
| Beauquier, J.,
90 |
| binary, (see alphabet / representation / string, binary) |
| Bird, M., 143, 302 |
| Boolean |
| | circuit, (see
circuit) |
| | expression, 215 |
| Borodin, A., 298, 302 |
| bounded-error, 258 - 259 |
| BPP, 262ff. |
| Braffort, P.,
305 |
| Büchi, J., 89, 302 |
| |
| canonically |
| | bigger / smaller, 4 |
| | ordered, 4 |
| cardinality of set, 299 |
| Cartesian product, 300 |
| cascade
composition, 89 |
| Chandra, A., 298, 302 |
| character, (see symbol) |
| Chomsky, N., 47, 90, 143, 197, 198,
302, 303 |
| Church, A., 47, 197, 303 |
| Church's thesis, 156 |
| circuit, 275 |
| | valued problem (CVP), 246,
247 |
| clique problem, 224, 246 |
| closure |
| | operation, the, (see Kleene closure) |
| | properties, 79 - 81, 89, 130
- 136, 142, 143, 193, 233 - 237, 241, 242, 246, 267 |
| | under an operation, 79 |
| Cobham, A., 246,
303 |
| COMMON PRAM, (see parallel random access machine, COMMON) |
| complementation, 6, 7, 80
- 81, 130, 133, 143, 193, 233, 236, 242, 246, 300 |
| complete / hard problem, 213, (see also P
-complete/ -hard problem) |
| complexity |
| | depth, 270ff., 273ff., 277 |
| | expected time, 249, 262 |
| | size, 270,
273, 277 |
| | space / time, 203 - 206, 262, 273 |
| composition, 7, 89, 142, 143, 221, 245 |
| computable
function, 35 |
| computation, 20, 58 - 60, 102 - 104, 153 |
| | accepting / nonaccepting / rejecting, 20, 58,
102, 152, 258 |
| | depth, 270, 273 |
| | deterministic / nondeterministic, 21 |
| | halting, 19, 21, 59 |
| | probabilistic, 249,
258 |
| concatenation, 3 |
| conditional accept / if instruction, 17, 19, 20 |
| configuration, 29, 55 - 56, 67, 110,
148 |
| | accepting / initial, 30, 56, 67, 99, 148 |
| configurations tree, 227, 236 |
| conjunctive normal form,
220 |
| connection language, 297 |
| Constable, R., 246, 304 |
| constant node, 275 |
| content of pushdown store,
100 |
| context-free grammar / language, 111ff., 187, 198, 238, 247 |
| context-sensitive grammar / language,
47, 186 - 187, 198 |
| Cook, S., 246, 298, 303 |
| countable set, 301 |
| countably infinite set, 173, 301 |
| CREW
PRAM, (see parallel random access machine, CREW) |
| cross product, 6 |
| cycle in graph,
301 |
| |
| Danthine, A., 89, 303 |
| decidability / partial decidability / undecidability, 32 - 35, 45 - 46, 47, 50, 82 -
84, 90, 136 - 138, 142 - 143, 173 - 179, 186, 188, 192ff., 195ff., 278, 289 |
| decision problem,
32 |
| defined value of function, 300 |
| DeLeeuw, K., 268, 303 |
| DeMorgan's law, 80 |
| depth |
| | of
circuit, 277ff. |
| | complexity, (see complexity, depth) |
| | of computation, (see computation, depth)
|
| derivation, 10 - 12 |
| | graph / tree, 12 |
| | leftmost, 12, 114 |
| deterministic |
| | assignment instruction, 17,
19 |
| | computation, (see computation, deterministic) |
| | looping instruction, 17, 19 |
| | program, 18 -
20 |
| | transducer / automaton / machine, 57, 66, 101, 110, 152 |
| diagonalization, 173, 195, 209,
289 |
| difference, 6, 300 |
| Diophantine polynomial / equation, 46, 50, 89, 244 |
| directed graph, 301 |
| disjoint
sets, 300 |
| DLOG, 205, 229 |
| domain of |
| | function / relation, 300 |
| | problem, 31 |
| | variables of program,
16 |
| DSPACE, 205, 225, 229, 236, 244, 245, 297 |
| DTIME, 205, 208, 227, 236, 242, 243 |
| DTIME_F,
282 |
| |
| -free finite-state automaton, 66 |
| transition rule, 66 |
| edge of graph, 301 |
| Edmonds, J., 246,
303 |
| Ehrenfeucht, A., 90, 303 |
| emptiness / nonemptiness problem, 36, 37, 45, 50, 82 - 83, 90, 136, 137,
143, 196, 238, 245, 246, 247 |
| empty |
| | pushdown store, 100 |
| | set, 299 |
| | string, 2 |
| | -word membership
problem, 34, 35, 196 |
| encoding, (see representation) |
| endmarker, left / right, 147 |
| eof -- end of
input file, (see conditional accept instruction) |
| equivalence / inequivalence problem, 36, 37,
45, 46, 47, 82, 84, 90, 136 - 137, 143, 190, 196, 198, 232, 246 |
| error-free probabilistic program,
248 - 251 |
| error probability, 258 - 259 |
| Evey, J., 143, 197, 303 |
| execution sequence, 18 -
25 |
| expected time complexity, (see complexity, expected time) |
| EXPTIME, 205, 213, 225,
229 |
| |
| family of circuits, 277ff. |
| final configuration / state, (see configuration / state, accepting) |
| finite
|
| | -domain / -memory program, 48ff. |
| | -state control, 55, 95, 145 |
| | -state transducer / automaton, 53 - 65,
130, 136, 142, 143, 190, 198, 232, 246 |
| Floyd, R., 47, 303 |
| FNC, 289 |
| formal language, 7 |
| Fortune, S.,
298, 303 |
| Freivalds, R., 268, 303 |
| function, 300 |
| | computed by, 258, 259, 275, 277, (see also relation
computed by) |
| |
| Garey, M., 247, 303 |
| gate, 275 |
| gcd, 301 |
| Gill, J., 267, 268, 303 |
| Goldschlager, L., 298, 304 |
| grammar, 8ff.,
11, 14 - 15 |
| graph, (see directed graph) |
| graph accessibility problem, 243 |
| Greibach, S., 143,
304 |
| Griffiths, T., 198, 304 |
| Grolmusz, V., 298, 304 |
| Gurari, E., 143, 304 |
| |
| halting |
| | computation, (see computation, halting) |
| | on input, 60 |
| | problem, 36, 82, 83, 138, 177, (see
also uniform halting problem) |
| hard problem, (see complete problem) |
| Harrison, M., 47,
304 |
| Hartmanis, J., 246, 304, 307 |
| Hilbert, D., 47, 304 |
| Hilbert's tenth problem, 46, 47 |
| Hirschberg,
D., 305 |
| Hong, J., 298, 304 |
| Hopcroft, J., 90, 143, 198, 247, 267, 302, 304 |
| Hunt, H., 246,
304 |
| |
| Ibarra, O., 143, 304 |
| Immerman, N., 247, 304 |
| initial |
| | configuration / state, (see configuration /
state, initial) |
| | value of variables, 16, 18 |
| input |
| | accepted / recognized, 21, 59, 103, 146,
153 |
| | alphabet / symbol, 52 - 53, 97, 146 |
| | head, 55, 95, 145 |
| | node, 275 |
| | nonaccepted / rejected, 21 |
| | of a
program, 18 |
| | tape, 55, 95, 145 |
| | value, 18 |
| instance of problem, 31 |
| instantaneous description, (see
configuration) |
| instruction segment, 29 |
| interpretation, 6 |
| intersection, 6, 7, 80 - 81, 130, 143, 193,
300 |
| inverse, 7 |
| |
| Johnson, D., 247, 268, 298, 303, 304 |
| Jones, N., 89, 143, 247, 304, 305 |
| |
| Kannan, R., 298, 305 |
| Karp, R., 246, 305 |
| Kindervater, G., 298, 305 |
| Kleene closure, 7 |
| Kleene, S., 90,
246, 305 |
| knapsack problem, 0 - 1/integer, 221, 244 |
Ku era, K., 298, 305 |
| Kuroda, S., 47,
198 |
| |
| Laaser, W., 247, 304 |
| Ladner, R., 247, 305 |
| Landweber, P., 198, 305 |
| language, 6 - 7,
11 |
| | accepted / recognized, 29, 61, 259 |
| | decided, 61, 277 |
| | generated, 11, 61 |
| LBA, (see linear bounded
automaton) |
| leaf of graph, 301 |
| left-hand side of production rule, 9 |
| left-linear grammar / language,
72 |
| length of |
| | derivation, 10 |
| | input / instance, 202 - 203, 205 - 206, 273 |
| | path in graph, 301 |
| | string, 2,
206 |
| Lenstra, J., 298, 305 |
| Lesk, M., 90, 305 |
| Levin, L., 246, 305 |
| Lewis, P., 246, 307 |
| LEX, 74,
90 |
| lexicographically, (see canonically) |
| linear bounded automaton (LBA), 156, 231 |
| log, 38,
204, 206 |
| logarithmic cost criterion, 201ff. |
| logspace |
| | -bounded Turing transducer / machine,
204 |
| | reducibility, 237 |
| LOOP program, 46, 47, 245, 246 |
| lower bound, 211 |
| Lueker, G., 246,
305 |
| |
| Maffioli, F., 268, 305 |
| Matijasevic, Y., 47, 305 |
| max, 301 |
| McCarthy, J., 143, 305 |
| McCulloch, W.,
89, 305 |
| Megiddo, N., 297, 305 |
| membership problem, 36, 37, 45, 142, 175 - 177, 186,
195, 197, (see also empty-word membership problem) |
| Meyer, A., 47, 306 |
| Miller, G., 90,
302 |
| Miller, R., 305 |
| min, 301 |
| mod, 252, 301 |
| Moore, E., 90, 268, 303, 306 |
| move, 56, 99, 149
- 150 |
| Muchnick, S., 89, 143, 304, 305 |
| Muller, D., 297 |
| multiset, 299 |
| Myhill, J., 90, 198,
306 |
| |
| natural number, 299 |
| NC, 289 |
| NLOG, 205, 229, 290 |
| node of graph, 301 |
| nonaccepting computation, (see
computation, nonaccepting) |
| noncomputable function, 35 |
| nondeterministic |
| | assignment instruction,
17, 24, 26 |
| | computation, (see computation, nondeterministic) |
| | looping instruction, 17, 22, 26 |
| | program,
18ff., 20, 21ff., 47 |
| | transducer / automaton / machine, 57, 66, 101, 152 |
| nonprimality problem, 242, 251
- 252, 267, (see also primality problem) |
| NOT gate, 275 |
| NP, 205, 213ff., 246, 264 |
| | -complete / -hard
problem, 213 - 225, 244 - 245, 246 |
| NSPACE, 205, 227, 229, 233, 241, 245, 246, 297 |
| NSPACE_ F,
292 |
| NTIME, 205, 225, 227, 233, 241 |
| |
| O notation, 204 |
| Oettinger, A., 143, 306 |
| O'hEigeartaigh, M., 305 |
| one-to-one function, 300 |
| onto
function, 300
|
| OR gate, 275 |
| ordered graph, 301 |
| output |
| | alphabet / symbol, 52 - 53, 97, 147 |
| | head, 55, 95, 145 |
| | node,
275 |
| | of, 21, 59, 103, 153, 258 |
| | tape, 55, 95, 145 |
| | undefined, 21, 59, 103, 153, 258 |
| |
| P, 205, 213, 229, 237 - 238, 291 |
| | -complete / -hard problem, 237 - 238, 246, 247, 291 |
| padded binary
representation, (see representation, padded binary) |
| parallel |
| | computation thesis, the, 281 |
| | program, 269
- 271 |
| | random access machine (PRAM), 272 - 275, 292 - 298 |
| | | COMMON / CREW / PRIORITY,
273 |
| | | TOLERANT, 296 |
| Parikh, R., 90, 303 |
| parse graph / tree, 12 |
| partial decidability / solvability, (see
decidability) |
| partially computable function, 35 |
| partition problem, 242, 246 |
| path in graph, 301 |
| PCP,
(see Post's correspondence problem) |
| Perles, M., 90, 143, 198, 302 |
| permutation, 3 |
| phrase structured
grammar / language, 8 |
| Pippenger, E., 298, 306 |
| Pitts, W., 89, 305 |
| polylog, 289 |
| polynomial |
| | expected
time bound / complexity, 262 |
| | expression, 45 |
| | space / time bound / complexity, 203, 262 |
| | time
reducibility, 212 |
| pop move, 100 |
| positive closure, 7 |
| Post, E., 198, 306 |
| Post's correspondence problem,
187 |
| power set, 299 |
| PRAM, (see parallel random access machine) |
| predecessor of node, 301 |
| predicate,
300 |
| prefix, 3 |
| Preparata, F., 297, 306 |
| primality problem, 202, (see also nonprimality problem)
|
| prime number, 202 |
| PRIORITY PRAM, (see parallel random access machine, PRIORITY)
|
| probabilistic |
| | computation thesis, the, 262 |
| | program, 249 |
| | Turing transducer / machine, (see Turing
transducer / machine, probabilistic) |
| problem, 31 |
| processor, 272 |
| production rule, 8 - 11 |
| program, 16ff.,
(see also probabilistic program; parallel program) |
| proper |
| | prefix / suffix of a string, 3 |
| | subset,
299 |
| PSPACE, 205, 225 - 237, 263 |
| | -complete / -hard problem, 213, 225, 230 - 233, 245,
246 |
| pumping lemma, 75, 90, 123, 143 |
| push move, 100 |
| pushdown |
| | alphabet / symbol, 109 |
| | head,
95 |
| | store / tape, 95 |
| | transducer / automaton, 95, 109, 130, 133, 142, 143, 191, 192, 197, 260,
267 |
| |
| Rabin, M., 47, 89, 267, 306 |
| Ragde, P., 298, 304 |
| random access machine (RAM), 200 - 201,
246 |
| random assignment instruction, 249 |
| range of function / relation, 300 |
| read instruction, 16,
19 |
| Reckhov, R., 246, 303 |
| recognition problem, 36 |
| recursion in programs, 91 - 93, 143 |
| recursive
|
| | finite-domain program, 92 - 95, 104 - 109, 143 |
| | language, 155, 187, 193 |
| recursively enumerable
language, 155, 174, 176, 179, 180, 193 |
| reducibility, 37 - 38, 173, 175, (see also logspace
reducibility; polynomial time reducibility) |
| regular |
| | expression / set, 73 - 74, 90 |
| | grammar / language,
65ff., 73, 74, 130, 143, 178, 198, 297 |
| reject instruction, 17, 19, 20 |
| rejecting computation, (see
nonaccepting computation) |
| relation, 300 |
| | induced by a problem, 32 |
| | computed by, 29, 61, (see also
function computed by) |
| representation, 5, 39ff., 205 - 206, 277 - 278 |
| | binary, 5 |
| | padded binary,
208 |
| | standard binary, 171 - 172, 174 |
| | unary, 5 |
| reverse of string (rev), 3 |
| right-hand side of production
rule, 9 |
| right-linear grammar / language, 72 |
| Rinnooy Kan, A., 305 |
| Ritchie, R., 47, 306 |
| root of graph,
301 |
| rooted graph, 301 |
| Rosier, L., 143, 304 |
| Rozenberg, G., 90, 303 |
| RP, 263 - 265 |
| Ruzzo, L., 298,
306 |
| |
| Sahni, S., 246, 304 |
| satisfiability problem, 215ff., 220ff. |
| Savitch, W., 246, 306 |
| Scheinberg, S., 143,
306 |
| Schutzenberger, M., 143, 198, 303, 306 |
| Schwartz, J., 268, 306 |
| Scott, D., 47, 89, 306 |
| sentence, 6,
10 |
| | symbol, (see symbol, sentence) |
| sentential form, 10 |
| sequential computation thesis, the, 204 |
| set,
299 |
| Sethi, R., 302 |
| Shamir, E., 90, 143, 198, 302 |
| Shannon, C., 268, 298, 303, 306 |
| Shapiro, N.,
268, 303 |
| Sheperdson, J., 89, 306 |
| Shiloach, Y., 298, 306 |
| single-valuedness problem, 36,
142 |
| Sipser, M., 247, 307 |
| size |
| | of circuit, 277 |
| | complexity, (see complexity, size) |
| SIZE, 282,
297 |
| SIZE_ F, 282 |
| Solovay, R., 267, 268, 307 |
| solution for a problem, 32 |
| solvability, 32 - 35, (see
also decidability) |
| space, 200, 201 - 205, 262 |
| | -bounded / complexity, (see complexity,
space) |
| | constructability, 208 |
| | hierarchy, 244 |
| speed-up theorem, linear, 244 |
| Speranza, M., 268,
305 |
| standard binary representation, (see representation, standard binary) |
| state, 51 - 53, 97, 104,
146 |
| | accepting / initial, 52, 53, 97, 147 |
| Stearns, R., 246, 304, 307 |
| Stockmeyer, L., 247, 298,
302, 307 |
| Strassen, V., 267, 268, 307 |
| string, 2 - 4, 6 |
| | binary, 2 |
| | unary, 2 |
| subgraph, 301 |
| subset,
299 |
| substring, 3 |
| successor of node, 301 |
| suffix, 3 |
| symbol, 2 |
| | auxiliary work-tape / input / output / push-
down, (see auxiliary work-tape / input /
output / pushdown alphabet) |
| | blank, 147 |
| | bottom pushdown, 97 |
| | sentence / start, 9 |
| | terminal / nonterminal,
8, 9 |
| | top, 100 |
| Szelepcsenyi, R., 247, 307 |
| |
| Thatcher, J., 305 |
| time, 200, 201 - 205, 262, 273 |
| | -bounded / complexity, (see complexity,
time) |
| | constructibility, 208 |
| | hierarchy, 199, 207, 246 |
| TOLERANT PRAM, (see parallel random access
machine, TOLERANT) |
| total function / relation, 300 |
| transition |
| | diagram, 53, 97, 147 |
| | rule, 52 - 53, 56 -
57, 97 - 98, 99, 147 |
| | table, 52, 53, 97, 147 |
| Traub, J., 306 |
| traveling-salesperson problem, 242, 246 |
| tree,
301 |
| Turing, A., 47, 197, 307 |
| Turing transducer / machine, 145ff., 155ff., 203ff. |
| | probabilistic, 258,
259 |
| | universal, 171 - 173, 197, 206 - 207 |
| two-way finite-state automaton, 245, 246 |
| Type
0 grammar / language, 8ff., 9ff., 179ff. |
| Type 1 grammar / language, 14, 47, 186 |
| Type 2
grammar / language, 14, 111ff. |
| Type 3 grammar / language, 15, 69ff. |
| |
| U_ DEPTH, 282, 297 |
| U_ DEPTH_ F, 282 |
| U_ FNC, 289, 292 |
| U_ NC, 238, 289, 290, 291, 297 |
| U_ SIZE,
282 |
| U_ SIZE_ F, 282 |
| U_ SIZE_ DEPTH_ F, 282, 293, 294 |
| Ullman, J., 89, 90, 143, 198, 247, 267, 302,
304 |
| unary alphabet / representation / string, (see alphabet / representation / string, unary) |
| uncountable
set, 301 |
| undecidability, (see decidability) |
| undefined |
| | output, (see output, undefined) |
| | value of function,
300 |
| uniform |
| | cost criterion, 202ff. |
| | family of circuits, 280ff.ff., 297 |
| | halting problem, 35 |
| union, 6, 7,
79, 81, 130, 136, 143, 193, 233, 236, 241, 300 |
| universal Turing transducer / machine,
(see Turing transducer / machine, universal) |
| universe, 300 |
| unsolvability, (see solvability)
|
| |
| Valiant, L., 143, 297, 298, 307 |
| Venn diagram, 299 |
| Vercellis, C., 268, 305
|
| vertex of graph, (see node of graph) |
| Vishkin, U., 298, 302, 306 |
| |
| Welsh, D., 268, 307 |
| word, (see sentence) |
| write |
| | conflict, 273 |
| | instruction, 16, 19 |
| Wyllie, J., 298,
303 |
| |
| XOR, 276 |
| |
| ZPP, 263 - 267
|