The Resource Problem solving in automata, languages, and complexity, Ding-Zhu Du, Ker-I Ko

Problem solving in automata, languages, and complexity, Ding-Zhu Du, Ker-I Ko

Label
Problem solving in automata, languages, and complexity
Title
Problem solving in automata, languages, and complexity
Statement of responsibility
Ding-Zhu Du, Ker-I Ko
Creator
Contributor
Subject
Language
eng
Cataloging source
UKM
http://library.link/vocab/creatorName
Du, Dingzhu
Illustrations
illustrations
Index
index present
LC call number
QA267
LC item number
.D8 2001
Literary form
non fiction
Nature of contents
bibliography
http://library.link/vocab/relatedWorkOrContributorName
Ko, Ker-I
http://library.link/vocab/subjectName
  • Machine theory
  • Formal languages
  • Computational complexity
  • Automates mathématiques, Théorie des
  • Langages formels
  • Complexité de calcul (Informatique)
  • Computational complexity
  • Formal languages
  • Machine theory
Label
Problem solving in automata, languages, and complexity, Ding-Zhu Du, Ker-I Ko
Instantiates
Publication
Note
"A Wiley-Interscience publication."
Bibliography note
Includes bibliographical references (p. 387-388) and index
Carrier category
volume
Carrier category code
  • nc
Carrier MARC source
rdacarrier
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
1. Regular Languages -- 1.1. Strings and Languages -- 1.2. Regular Languages and Regular Expressions -- 1.3. Graph Representations for Regular Expressions -- 2. Finite Automata -- 2.1. Deterministic Finite Automata -- 2.2. Examples of Deterministic Finite Automata -- 2.3. Nondeterministic Finite Automata -- 2.4. Converting an NFA to a DFA -- 2.5. Finite Automata and Regular Expressions -- 2.6. Closure Properties of Regular Languages -- 2.7. Minimum Deterministic Finite Automata -- 2.8. Pumping Lemmas -- 3. Context-Free Languages -- 3.1. Context-Free Grammars -- 3.2. More Examples of Context-Free Grammars -- 3.3. Parsing and Ambiguity -- 3.4. Pushdown Automata -- 3.5. Pushdown Automata and Context-Free Grammars -- 3.6. Pumping Lemmas for Context-Free Languages -- 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 Godel 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. Asymptotic Growth Rate -- 6.2. Time and Space Complexity -- 6.3. Hierarchy Theorems -- 6.4. Nondeterministic Turing Machines -- 6.5. Context-Sensitive Languages -- 7. NP-Completeness -- 7.1. NP -- 7.2. Polynomial-Time Reducibility -- 7.3. Cook's Theorem -- 7.4. More NP-Complete Problems -- 7.5. NP-Complete Optimization Problems
Dimensions
25 cm
Extent
viii, 396 pages
Isbn
9780471439608
Lccn
2001275892
Media category
unmediated
Media MARC source
rdamedia
Media type code
  • n
Other physical details
illustrations
System control number
  • (OCoLC)48222937
  • (OCoLC)ocm48222937
Label
Problem solving in automata, languages, and complexity, Ding-Zhu Du, Ker-I Ko
Publication
Note
"A Wiley-Interscience publication."
Bibliography note
Includes bibliographical references (p. 387-388) and index
Carrier category
volume
Carrier category code
  • nc
Carrier MARC source
rdacarrier
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
Contents
1. Regular Languages -- 1.1. Strings and Languages -- 1.2. Regular Languages and Regular Expressions -- 1.3. Graph Representations for Regular Expressions -- 2. Finite Automata -- 2.1. Deterministic Finite Automata -- 2.2. Examples of Deterministic Finite Automata -- 2.3. Nondeterministic Finite Automata -- 2.4. Converting an NFA to a DFA -- 2.5. Finite Automata and Regular Expressions -- 2.6. Closure Properties of Regular Languages -- 2.7. Minimum Deterministic Finite Automata -- 2.8. Pumping Lemmas -- 3. Context-Free Languages -- 3.1. Context-Free Grammars -- 3.2. More Examples of Context-Free Grammars -- 3.3. Parsing and Ambiguity -- 3.4. Pushdown Automata -- 3.5. Pushdown Automata and Context-Free Grammars -- 3.6. Pumping Lemmas for Context-Free Languages -- 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 Godel 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. Asymptotic Growth Rate -- 6.2. Time and Space Complexity -- 6.3. Hierarchy Theorems -- 6.4. Nondeterministic Turing Machines -- 6.5. Context-Sensitive Languages -- 7. NP-Completeness -- 7.1. NP -- 7.2. Polynomial-Time Reducibility -- 7.3. Cook's Theorem -- 7.4. More NP-Complete Problems -- 7.5. NP-Complete Optimization Problems
Dimensions
25 cm
Extent
viii, 396 pages
Isbn
9780471439608
Lccn
2001275892
Media category
unmediated
Media MARC source
rdamedia
Media type code
  • n
Other physical details
illustrations
System control number
  • (OCoLC)48222937
  • (OCoLC)ocm48222937

Library Locations

  • African Studies LibraryBorrow it
    771 Commonwealth Avenue, 6th Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Alumni Medical LibraryBorrow it
    72 East Concord Street, Boston, MA, 02118, US
    42.336388 -71.072393
  • Astronomy LibraryBorrow it
    725 Commonwealth Avenue, 6th Floor, Boston, MA, 02445, US
    42.350259 -71.105717
  • Fineman and Pappas Law LibrariesBorrow it
    765 Commonwealth Avenue, Boston, MA, 02215, US
    42.350979 -71.107023
  • Frederick S. Pardee Management LibraryBorrow it
    595 Commonwealth Avenue, Boston, MA, 02215, US
    42.349626 -71.099547
  • Howard Gotlieb Archival Research CenterBorrow it
    771 Commonwealth Avenue, 5th Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Mugar Memorial LibraryBorrow it
    771 Commonwealth Avenue, Boston, MA, 02215, US
    42.350723 -71.108227
  • Music LibraryBorrow it
    771 Commonwealth Avenue, 2nd Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Pikering Educational Resources LibraryBorrow it
    2 Silber Way, Boston, MA, 02215, US
    42.349804 -71.101425
  • School of Theology LibraryBorrow it
    745 Commonwealth Avenue, 2nd Floor, Boston, MA, 02215, US
    42.350494 -71.107235
  • Science & Engineering LibraryBorrow it
    38 Cummington Mall, Boston, MA, 02215, US
    42.348472 -71.102257
  • Stone Science LibraryBorrow it
    675 Commonwealth Avenue, Boston, MA, 02445, US
    42.350103 -71.103784
Processing Feedback ...