Авторизация
Поиск по указателям
Jones N.D. — Computability and complexity from a programming perspective
Обсудите книгу на научном форуме Нашли опечатку?
Название: Computability and complexity from a programming perspectiveАвтор: Jones N.D. Аннотация: "Neil Jones is one of the precious few computer scientists with great expertise and leadership roles in both formal methods and complexity. This makes his book especially valuable." — Yuri Gurevich, Professor of Computer Science, University of Michigan
Язык: Рубрика: Computer science /Статус предметного указателя: Готов указатель с номерами страниц ed2k: ed2k stats Год издания: 1997Количество страниц: 457Добавлена в каталог: 01.12.2013Операции: Положить на полку |
Скопировать ссылку для форума | Скопировать ID
Предметный указатель
Hilbert, D. 167 Horn clause 391 i 72 Implements 52 Implication 192 Indirect fetch 119 Indirect store 119 Induction 439 Induction, complete 439 Induction, course-of-values 439 Induction, hypothesis 439 Inference relation 195 Inference rule 189 Inference system 188 195 Infinite sequence 424 Initial store 264 Intensional 226 240 Interpreter 54 Interpreter, efficient 286 Interpreter, overhead 90 Interpreting function 54 Invariance 241 Invariance Thesis 21 Isomorphism theorem 231 judgment 189 LAMBDA 140 Lambda calculus 8 Lambda notation 427 Language, accepted by DFA 437 Language, accepted by NFA 437 Language, equivalent 48 Language, functional 137 Language, imperative 137 Language, implementation 53 58 Language, simulating one by another 48 Language, source 53 57 Language, target 57 Left-most multi-step derivation relation 433 Left-most one-step derivation relation 433 Length (of a list) 33 Length of a read-only TMro state 317 Length of a state 316 Linear time 276 291 Linearly equivalent 252 LINTIME 272 276 LIST 33 35 List representation 33 Literal 419 Logarithmic cost 255 257 LOGSPACB 319 322 346 351 LOGSPACE functions 325 lookup 55 Markov algorithms 8 Match 40 57 MCV 390 Minimization 208 Model-independent 225 Monotone circuit 383 Multi-step derivation relation 433 Multi-step rewrite relation 153 n-tuples 422 Natural numbers 421 Natural semantics 188 Negation 32 192 419 NFA 436 NLINTIME 378 NLOGSPACE 333 345 346 nodes 430 Non-deterministic finite automaton 436 Nondeterminism 243 331 Nonterminals 432 Nonuniform complexity xv Normal form 142 Normal Form Theorem 210 Normalizations 335 NPSPACE 333 345 346 NPTIME 243 333 346 Numerals 34 o-notation 429 Omega-notation 429 One-step derivation relation 433 One-step rewrite relation 153 Operational semantics 188 Optimality of a specializer 103 Ordered pair 422 Overhead factor 252 Pairing 53 Pairing decomposition 442 Parallelism xv Parallelism, PTIME 395 Partial evaluation 65 77 96 Partial evaluation, off-line 106 Partial evaluation, techniques 104 Partial recursive 205 Partial recursive functions 24 Pascal-like implementation of GOTO 266 Path finding 332 Pattern 40 PCP 156 Polynomial-time 274 Polynomially equivalent 252 Post's correspondence problem 156 Predecessor 34 Predicate 192 195 Prefix 431 Primitive recursion 206 Problem 3 Problem, ambiguity 161 434 Problem, complete for NLINTIME 378 Problem, complete for NLOGSPACE 376 Problem, complete for RE 375 Problem, completeness 161 434 Problem, membership 434 Problem, natural unsolvable 151 Problem, non-emptiness for 434 Problem, representation 271 Problem, representation of 368 Problem, undeddable 154 Production 153 Program padding 233 Program point specialization 105 Program property 79 Program property, extensional 79 Program property, intensional 79 Program property, nontrivial 79 Program spedalizer 58 227 Program spedalizer, optimal 103 Program, boolean 407 Program, computes a function 38 Program, function computed by 38 Program, looping 38 Program, self-reproducing 222 Program, stack 288 Program, terminating 38 Program, time-bounded 271 Program, timed universal 288 Program-dependent 253 256 Program-independent 253 Programming language 47 Programs, cons-free 349 355 Proof tree 197 Propositional formulas 419 Provability 202 PSPACE 319 322 345 346 407 PTIME 244 272 275 322 345 346 355 Pushdown automaton 359 Quadruples 422 Quantified boolean algebra 409 r.e. see "Recursively enumerable" RAM 111 Random access machine 8 118 read-only 315 Readin 113 Readout 113 Real numbers xv 421 Real numbers, positive 421 Recursion theorem 220 229 RECURSIVE 86 Recursive extension 355 Recursive function 8 205 Recursive function theory 205 Recursively enumerable 86 195 197 202 Redex 142 Reducing SAT to CLIQUE 370 Reduction 152 365 366 Reduction function 368 Reflexive extension 222 REGALL 434 REGAMB 434 Regular expression 435 Regular expression, set generated by 435 Regular expression, totality 412 Regular grammar see "Grammar" Representable predicate 200 Resource bound 271 332 Resources 242 Restriction to one operator 60 Restriction to one variable 61 reverse 30 432 Rewrite rule 153 Rice's theorem 78 Robust 147 274 276 322 Robustness 241 271 Robustness, computability 127 Rogers, H 226 231 Rooted DSG 262 Running time 275 Running time function 90 Running time, WHILE program 254 Russell's paradox 15 s-m-n function property 227 SAT 367 370 397 Satisfiable 443 Second component 422 Self-interpreter 72 227 Self-reproducing program 222 Semantic function 47 90 Semi-decidable 76 Semi-Thue 153 Set 421 Set, contained in 421 Set, countable 14 Set, deciding membership of 10 Set, difference 422 Set, Diophantine 169 Set, element of 421 Set, empty 421 Set, equality 421 Set, exponential Diophantine 169 Set, intersection 422 Set, member of 421 Set, union 422 Simulation with data change 129 Simulation, invariant 135 Single-assignment 383 Size (of a tree) 29 Slowdown 252 Software viewpoint 9 solvable 4 Source program 50 Space usage 332 SPACE(f) 319 Space-bounded programs 319 Space-constructible 328 Specialization 205 Specializing function 59 Spedalizer 59 Spedalizer properties, computational completeness 102 Spedalizer properties, optimality 103 Spedalizer properties, totality 102 Speedup 252 SRAM 119 Stack programs 288 359 Start state 436 437 Start symbol 432 State 112 114 264 State transition graph 337 343 State, terminal 112 States (of an DFA) 437 States (of an NFA) 436 Stochastic algorithms xv Storage Modification Machine 255 STORE 36 37 112 114 137 189 264 Store, initial 37 String 431 String matching 359 360 String rewriting 153 String, accepted by DFA 437 String, accepted by NFA 437 String, bit 250 String, concatenation 431 String, configuration 155 String, empty 431 Strongly linearly equivalent 253 Structural operational semantics 188 Sublinear 315 Subset 421 Substring 431 Successor 34 Successor random access machine 119 Suffix 431 Superlinear time 292 Symbolic computation 105 symbols 431 Tape alphabet 115 Terminals 432 Theorem 196 Theorem, normal form 129 Theta-notation 429 TI-diagrams 51 Time constructible 293 297 Time usage 332 TIME(f) 272 Time, linear 276 Time, superlinear 292 Timed programming language 89 Timed universal program 288 TM 111 TMro 316 Totality of a spedalizer 102 Tractable 244 Transition function 436 437 Treeless transformer 353 Triples 422 TRUE 32 419 Truth 202 Truth assignment 420 Truth table 420 Truth values 419 Tupling function 225 Turing completeness 227 Turing machine 5 8 115 316 Turing machine, configuration 122 Turing machine, deterministic 121 Turing machine, enumeration 225 Turing machine, program 225 Uncomputable function see "Undecidable" Uncomputable functions 16 Undecidable 78 154 Undirected graph 431
Реклама
|
|
О проекте