Problem Solving in Automata, Languages, and Complexity

4 Turing Machines

4.1 One-Tape Turing Machines

4.2 Examples of Turing Machines

4.3 Multi-Tape Turing Machines
- 4.4 Church-Turing Thesis
- 4.5 Unrestricted Grammars
- 4.6 Primitive Recursive Functions
- 4.7 Pairing Functions and Gijdel Numberings
- 4.8 Partial Recursive Functions

5 Computability Theory
- 5.1 Universal Turing Machines
- 5.2 R. E. Sets and Recursive Sets
  - 5.3 Diagonalization
  - 5.4 Reducibility
  - 5.5 Recursion Theorem
  - 5.6 Undecidable Problems

6 Computational Complexity
- - 6:
  - 1. 7 NP
  - - - Completeness Context-Sensitive Languages
        
        NP
        
        Polynomial-Time Reducibility
        
        Cook’s Theorem
        
        More NP-Complete Problems
        
        NP-Complete Optimization Problems

References

Index

V, 62,

A,

1,

CD,

\

4: 216,

(gi)i<m -

(Vi)i<m -

(4 i>,

(m, n2, , nk),

[f-u, n2, .., nk],

< -my

g.&,

I,',

r;,

t-, 123,

tjj,

t-*, 123,

t-j-j,

A,

A*,

A+,

A”,

AR,

A-B,

A $ B,

A\&

A v B,
- AB,
- A-rule,
- Ackermann function,
- Adjacency matrix,
- Alphabet,
  - binary,
    - Roman,
    - Arabic digit,
- Ambiguity,
- Approximation problem,
- Approximation ratio,
- Arden’s lemma,
- BIN PACKING (BP), 364, Assignment, see Boolean function
- Binary string,
- Boolean algebra,
- Boolean formula,
  - clause,
    - conjunctive normal form (CNF),
    - disjunctive normal form (DNF) ,
  - literal,
    - satisfiable,
- Boolean function, 204,
  - assignment,
    - truth,
  - associative law,
  - commutative law,
  - De Morgan’s law,
- ```
- distributive law, 390 INDEX

   - BOTTLENECK STEINERTREE (BST),
```
- BOUNDED PCP,
- BOUNDED TILING,

Busy beaver function, TREE

Busy beaver problem,

Certificate,

Changing base,

Characteristic function, 164,

XL, 164,
- extended, Church-Turing Thesis, 1%

Clause,

Clock machine,

CNF-SAT, CNF, see Conjunctive normal form

co- NP,

co-r.e. set,

COINF,

Complementation, of a set,

Composition, complete set

Computation path,
- Computational model, reasonable,

Concatenation, of lanugages,
- of strings,

Conjunction,
- nonpolar representation, see also (k, Q-CNF
- polar representation,

CONNECTED-VC,

Constant function,

Context-free grammar,
- ambiguous, 112,
- generating a sentence,
- left-factoring,
- leftmost graph,
- linear,
- nonterminal symbol,
- starting symbol,
- strong LL(lc),
  - terminal symbol,
  - Context-free language,
    - inherently ambiguous,
  - Context-sensitive grammar,
  - Context-sensitive language,
    - CONVEX PARTITION,
  - Cook’s theorem,
  - Crossing sequence, 173,
  - CUBIC VC,
  - De Morgan’s law,
  - Decision problem, 243,
  - Degree of unsolvability,
  - Derivation,
    - leftmost,
  - Derivation tree,
    - Deterministic finite automata (DFA),
    - accepting a language,
    - accepting an input string, 24,
    - computation path,
    - final state,
    - finite control,
    - initial state,
    - minimum,
    - product automata,
    - rejecting an input string,
      - states,
        
        (state) transition function, 23,
    - tape,
      - tape head,
    - transition diagram,
  - Diagonalization, 241, DGIso, see DIGRAPH ISOMORPHISM
    - space-bounded,
      - DIGRAPH ISOMORPHISM (DGIso),
    - in-edge, Directed graph, 16; see also Graph
    - out-edge, labeled, see Labeled digraph
  - Disjunction,

INDEX

Dovetailing, DNF, see Disjunctive normal form

Dynamic programming, DTM, see Turing machine

&,

E-rule,

EDGE COLORING,

EIGHT-QUEEN PROBLEM,

Elementary product,

Elementary sum,

EMP,

Empty string,

Enumeration theorem,

Equivalence class,

Equivalence relation,

Existential quantifier, bounded,

Exponential functions,

EUCLIDEAN TSP,

f'"',

f(n) -( s(n),

Feasible problem,

Feasibly solvable language,

Fibonacci function,

FIN,
- Fully space-constructible function,

Fully time-constructible function,

Ackermann, tion

constant,

exponential,

growth rate,

increasing,

initial,

pairing, function

partial,
- poly-log, function
- polynomial,
  - 337, polynomial-time computable,
- polynomially honest,
- primitive recursive, 201,
- projection,
- recursive,
- subexponential,
- successor,
  - superexponential,
  - threshold,
  - total,
    - Turing-computable, 164, 168,
- zero,
- Function-index set,
- GIA,
- G(r),
- Gap theorem,
- Gijdel numbering, GIso, see GRAPH ISOMORPHISM
  - Grammar, 90,
    - context-sensitive, grammar
    - left-linear,
    - linear,
    - right-linear,
    - unrestricted,
    - isomorphic, graph
    - adjacency matrix,
    - cubic,
    - cycle,
    - edge,
    - edge-square,
    - loop,
    - path,
    - planar,
      - vertex,
      - vertex cover,
        
        GRAPH AUTOMORPHISM (GAuTo),

GRAPH ISOMORPHISM (GIso), 392 INDEX

Growth rate,

Guess-and-verify algorithm, 307,

Halting problem,

Hamiltonian cycle,

HAMILTONIAN CYCLE (HC),

HITTING SET (HS), HC, see HAMILTONIAN CYCLE

Homomorphism,

if-then-else, HS, see HITTING SET

Increasing function,

Independent set,

INDEPENDENT SET (IS),

Index(R),

Induced subgraph, Function-index set

Induction, mathematical,

Inductive definition,

INF,

Inherent ambiguity,

Initial functions,

Integer factoring,

INTEGER PROGRAMMING (IP),

Intersection,

L~,

Isomorphic graphs, IS, see INDEPENDENT SET

Isomorphism function,
- item(n),

Ii;",

(k, !)-CNF,

@$)-SAT,

&MINIMUM SPANNING TREE,

Kleene closure,
- KNAPSACK, 363,
- KNIGHT’S TOUR,

Kolmogorov complexity,
- L(G),
- L(M), 24, 25,
- L(r),
- L&52,
- L$’
  - l(n),
    - L’Hopital’s rule,
    - Labeled digraph, 17,
      - e-edge,
      - final vertex,
      - initial vertex,
        
        Labeled Markov algorithm (LMA) ,
    - Language,
      - context-sensitive, language
      - feasibly solvable,
      - linear,
        
        quotient,
      - reversal of a, regular, see Regular language
        
        Turing-acceptable,
        
        Turing-decidable,
    - Language equation,
    - Left-factoring,
    - Left-linear grammar,
    - Lexicographic ordering,
    - Linear grammar,
  - Linear language,
    - Linear set,
    - Linear speed-up theorem,
    - Literal,
  - Lookahead set, LMA, see Labeled Markov algorithm
    - LONGEST PATH (LP),
    - M, LP, see LONGEST PATH
    - Mn,
    - Mz,
    - MI Xi&,
    - Mathematical induction,
    - MAX(L), 67,
      - MAX-CLIQUE,
      - MAX-SSAT,
      - MAX-3SAT-b,
      - (min i)i~~, GRAPH
    - MIN(L), 61,
      - MIN-VC,
      - Minimization, bounded,

INDEX

(MCG), MINIMUM CONNECTIVITY GRAPH

Minimum DFA,

Multi-valued function,

polynomial-time computable,

N,l

Negation,

NETWORK SMT,

(NFA), Nondeterministic finite automata

accepting an input, 39,

computation path,

computation tree,

e-closure,

e-move,

e-transition,

hanging,

multiple-state transition,

transition diagram,
- (NTM), Nondeterministic Turing machine

accepting an input,

computation tree,

computing a function,

space complexity,

time complexity,

Nonterminal symbol,
- NP, 309,
- NP-complete set,
  - search problem,
- NP-hard set,
- NPSPA CE,
- NSPACE(t(n)),
- NTIME(t(n)),
- Ogden’s lemma, machine
- Optimization problem,
  - polynomially bounded, tion problem
  - Oracle,
  - Pairing function,
  - Parikh’s lemma,
    - Parse tree,
    - Parsing,
      - top-down,
    - Partial function,
    - PARTITION, sive function
    - Partition,
      - even,
    - &, PDA, see Pushdown automata
    - ?r,k,
    - PLANAR CONNECTED-VC-4,
    - PLANAR NONPOLAR-3SAT,
      - PLANAR POLAR-%AT,
      - PLANAR VC, 369,
    - Poly-log functions,
    - Polygon, convex,
      - rectilinear,
    - Polynomial functions,
      - scheme (PTAS), Polynomial-time approximation
      - fully (FPTAS),
        
        tion, 337, Polynomial-time computable func-
      - Polynomial-time equivalence,
      - Polynomially honest function,
      - Positive closure,
        
        (PCP), POST CORRESPONDENCE PROBLEM
      - Predicate,
      - Prefix,
      - prefix(B),
        
        PRIMALITY TESTING (PRIME),
      - Primitive recursion, PRIME, see PRIMALITY TESTING
        
        Primitive recursive function, 201,
        
        Primitive recursive set,
        
        Probabilistically checkable proofs,
        
        Product automata,
        
        Productive set,
        
        Program-size complexity,
        
        Projection function,
        
        Projection theorem,
- for regular languages, Pumping lemma
  - strong form,
- for context-free languages,

Pushdown automata (PDA),
- accepting an input, 123,
- configuration,
  - successor,
- deterministic,
- linear-bounded,
- product,
  - two-stack,

Quotient language,

RL,

R;,

T-APPROX-BST,

r-APPROX-LP,

r-APPROX-n,

r-&‘PRoX-3sAT,

r-APPROX-3SAT-3,

r-APPROX-TSP,

r-APPROX-VC,

r-APPROX-VC-d,

r(n),

r(n)-APPROX-CLIQUE,

Random access machine (RAM), RAM, see Random access machine

REC,

RECTANGULAR PARTITION,

RECTILINEAR SMT,

Recursion theorem,

Recursive definition,

Recursive function(s),

partial, 215,
- enumeration of,
- extendable,

primitive, 201,

Recursive set, 215,
- primitive,
  - 215, Recursively enumerable (r.e.) set(s),
- enumeration of, 228,
- complete,

Recursively separable sets,

Reducibility,
- approximation-preserving,
- many-one,
  - polynomial-time,
- polynomial-time,
- Turing, polynomial-time,
- Reduction function,
- REG,
- Regular expression,
  - disjunctive normal form,
  - distributive law,
  - extended,
  - preference rules,
  - starless,
    - LENCE, REGULAR EXPRESSION NONEQUIVA-
- Regular grammar,
- Regular language,
- Regular set,
  - REV,
- Reversal, of a language,
  - of a string,
- Rice’s theorem,
  - for r. e. index sets,
- Right-linear grammar,
  - S-m-n theorem,
  - SATISFIABILITY (SAT), SAT, see SATISFIABILITY
- Savitch’s theorem,
- Search problem,
  - W-complete,
  - Self-recognizing program,
  - Self-referential program,
  - Self-reproducing program,
  - Semi-characteristic function,
- Semilinear set,
- Sentence, 89,
  - Sentential form, 89,
    - left,
  - Set-index set,
    - nontrivial,
  - c*, SGIso, see SUBGRAPH ISOMORPHISM
  - a,
  - DA,
  - Simple set,
    - size(n),
  - SpaceM(x), SMT, see STEINER MINIMUM TREE

Space complexity, INDEX

Space-constructible function, fully,

Space hierarchy theorem,

for NSPA CE,

Space marking machine,

Spanning tree,

SQRT(L), 67,

Star closure,

Steiner minimum tree,

STEINER MINIMUM TREE (SMT),

Steiner tree,
- Steiner points,
- terminal points,

String,
- binary,
- empty,
- length,

Subexponential functions,
- SUBGRAPH ISOMORPHISM (SGIso),

Subset construction,

Substitution,

Substring,

Subtraction, of sets,
- Successor function,
- suffix,
- Superexponential functions,
- Symbol,

T n,ky
- Tape compression theorem,
- Terminal symbol,
- Three-dimensional matching, MATCHING
  - (3DM), THREE-DIMENSIONAL MATCHING
- SSAT,
- BSAT-EXACTLY-ONE,
- 3&w--NOT-ALL,
- Threshold function,
- TILING,
- TimeM( 286,
- Time complexity,
  - Time-constructible function, fully,
  - Time hierarchy theorem,
    - TOT, TM, see Turing machine
    - Total function,
    - TOWER OF HANOI,
      - Transition diagram,
        
        (TSP), 339, TRAVELING SALESMAN PROBLEM
        
        WITH (1,2)-DISTANCE,
        
        WITH TRIANGLE INEQUALITY,
      - Tree,
      - Truth assignment,
      - Truth table,
      - Turing-acceptable language, PROBLEM
        
        168, Turing-computable function, 164,
      - Turing-decidable language,
      - Turing-enumerable set,
      - Turing machine(s) (TM, DTM),
        
        accepting an input,
        
        coding of,
        
        computation path,
        
        computing a function,
        
        configuration,
        
        successor,
        
        deterministic (DTM),
        
        enumeration,
        
        instructions,
        
        legal code of a,
        
        memory space,
        
        multi-tape,
        
        configuration,
        
        transition function,
        
        one-pebble, ministic Turing machine
        
        output,
        
        product,
        
        read/erase-only,
        
        read-only,
        
        crossing sequence,
        
        running time,
        
        space bound,
        
        standard one-worktape,
        
        state,
        
        final,
        
        initial,
- tape, 396 INDEX
  - input,
  - one-way write-only,
  - output,
  - read-only,
  - storage,
  - tracks,
  - work,
- tape alphabet,
- time bound,
  - transition diagram,
  - transition function,
  - two-dimensional,
  - two-way,
  - two-way-infinite one-tape,
  - universal,

2',

%AT,

Ultimately periodic set,

Unbounded minimization,

Undecidable problem, 243, 251,

Undirected graph,

Union,

Universal quantifier, bounded,
- Universal Turing machine,
- Unrestricted grammar,
- Unsolvability, degree of,
- Unsolvable problem,
- vc*(G), VC, see VERTEX COVER
- VERTEX COLORING,
  - Vertex cover,
  - VERTEX COVER (VC),
  - Wn,
  - Witness,
  - Word,
  - Word equation,
  - Word theory,
  - X-Y,
  - xvy,
  - XR
  - Xk
  - 5,
  - Zero function,

Problem Solving in Automata, Languages, and Complexity

Get our desktop app

Company

Features

Documentation

Resources