1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 76
Текст из файла (страница 76)
A., 244Markov system, or Markov algorithm,232MAX 2-SAT, 316~7MAX SAT, 314-6, 336,347McNaughton, R., 110Mealy, G. H., 110member, or element, of a set, 5Miller, G. A., 175minimal element of a partial order,18minimalizable function, 239minimalization, 238minimum equivalent finite automaton, 105, 330--1minimum spanning tree, 350Minsky, M. L., 243Moore, E. F., 110Morris, J. H., Jr., 111Morse, S. P., 177jl-recursive function, 239nn-ary relation, 10358Nam., -e., \1;)negative literal, 288neighborhood, or neighborhood relation, 345Nerode, A., 111n-fold Cartesian product, 10node, 14, 123NODE COVER, 284, 327~8, 335~7nondeterminism, 2, 63, 158, 221, 292nondeterministic finite automaton, 65nondeterministic 2-tape finite automaton, 85nondeterministic 'lUring machine, 221~~~~"~""'~"\.'"~~~"'~"~N'P,293nonterminal, 115, 228nonerasing homomorphism, 299NP,293NP-complete problems, 301~350ooccurrence, 42Oettinger, A.
G., 175Ogden, W. G., 176one-to-one function, 11onto function, 11OI, \.}, '2'6~order of a function, 0(·), 32ordered pair, 9ordered triple, 10ordered tuple, 10output of a machine, 196pP, 275~277Papadimitriou, C. H., 244, 300, 351parse tree, 123parser, 58, 163~70partial order, 17Index\' ~~~\~\.<:)~ ;l.~1. ;l.~~ ,'l.~~ ;~\.,~7, 326~7partition of a set, 8partly approximable problem, 336path, 18, 145Perles, M., 110, 176Polya, G., 52polynomially balanced language, 298polynomially bounded 'lUring machine,276, 293polynomially decidable, 276polynomial-time algorithm, 276polynomial red uction between two lan~~,,~~~~~'\..polynomial Turing reduction, 309pop, 131positive literals, 288Post correspondence system, 262Post, E. L., 243, 273power set, 8Pratt, V.
R., 111precedence relation, 172precedes, -<, 124~6prefix, 43, 83primitive recursive function, 234primitive recursive predicate, 236problem, 279program counter, 211program of a random access Turingmachine, 211proper subset, 6push, 131purge algorithm for 2-SAT, 291, 342pushdown automaton, 131~9deterministic, 158-75and context-free languages, 136~42simple, 139~41pushdown store, or stack, 131Indexq359root of a parse tree, 123root of a tree, 334rule of a grammar, 114-5, 227-8quadruple, 10quintuple, 10quotient of languages, 985rSalomaa, A., 53Rabin, M.
0., 110random access 'lUring machine, 211range of a function, 11rate of growth of a function, 32REACHABILITY, 279-80reading head, 56Reckhow, R. A., 244recursive function, 196recursive language, 195recursively enumerable language, 198reduce move of a parser, 171reduction from a language to another,254polynomial, 302Reeves, C. R., 351refinement of an equi valence relation,20, 95reflexive relation, 14reflexive transitive closure, 30register of a random access Turingmachine, 211regular expression, 48regular language, 50, 75-91, 119rejecting configuration, 194rejects, 194, 216RELIABLE GRAPH, 332reversal, R, 43rewriting system, 228right quotient of languages, 83, 148right-linear grammar, 122rightmost derivation, 127Rivest, R.
1., 53Rogers, H., Jr., 244290-8, 301-4, 30818satisfiable Boolean formula, 289satisfying truth assignment, 289Schutzenberger, M. P., 176-7Scott, D., 110self-embedding grammar, 149self-reducibilityy, 287, 340semidecides, 198, 216, 222sequence, 10set, 5SET COVER, 332Sethi, R., 177sextuple, 10Shamir, E., 110, 176Shepherdson, J. C., 111shift move of a parser, 171similar, 125simple, 139simulated annealing, 348-9singleton, 5single-turn pushdown automaton, 143Sipser, M., 244solution of a problem, 340-9stack symbols, 131standard automaton for a regular language, 96standard derivation, 259star height of a regural expression,52*-free regular expressions, 329start symbol, 115, 228state, 56-7, 65, 115, 131, 181state diagram, 59SATISFIABILITY,360IndexStearns, R.
E., 177, 299Steiglitz, K., 351step, 116, 132, 185, 276string, 42string matching, 108SUBGRAPH ISOMORPHISM,332subsequence, 83subset, 6substring, 43successor function, 234suffix, 43, 83symbol, 42symmetric relation, 14ttape, 57, 180,201-9,212332temperature, 349terminal symbol, 115, 228ternary relation, 10 item Thompson,K.,1113-COLORING, 3083-SATISFIABILITY, 313, 317, 323, 326,333tile, 262tiling problem, 263-7, 310-3tiling system, 262top-down parser, 163total order, 18transformation of a configuration, 189transition, 66, 131transition function, 57, 181, 202,transition relation, 66, 131, 222transitive relation, 16TRAVELING SALESMAN PROBLEM, 276,282-3,297-8,301,318,324,338-9, 345-9tree, 333true, T, 289truth assignment, 289TAXICAB RIPOFF,Turing, A.
M., 2, 179, 243Turing machine, 179-226,as algorithm, 179, 245-7computation by a -, 194-200k-tape, 201-8with multiple heads, 208with two-dimensional tapes, 208with random access, 210-9nondeterministic, 221-6, 292-4universal, 247-50efficient, 275-92polynomially bounded 276-92exponentially bounded, 296Turing-enumerable language, 268TWO-MACHINE SCHEDULING, 305-7,326, 336-7two-way finite automaton, 1012-change neighborhood, 3472-head finite automaton, 91, 2622-SATISFIABILITY, 290-2, 313-5, 323,3332-tape finite automaton, 62-3uUllian, J.
S., 177Ullman, J. D., 177,244unary function, 10unary notation, 90UNARY PARTITION, 286uncountable set, 21, 28-9universal Turing machine, 247-50undecidable language, 254-71undirected graph, 15UNDIRECTED HAMILTON CYCLE, 3224unicursal, 281union of sets, 6unrestricted grammar, 228unsatisfiable Boolean formula, 290unsolvable problem, 254-71IndexvValiant, L. G., 176value of a function, 11wWang, H., 273Warshall, S., 53weak precedence grammar, 173witness, or certificate, 297yYamada, H., 110yield of a parse tree, 123yields, f-*, 58, 185, 212yields in one step, f-, 66, 132, 212Young, P. R., 244Younger, D.
H., 176zzero function, 234361.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
