"Introduction to Automata Theory, Languages, and Computation"
E305925
"Introduction to Automata Theory, Languages, and Computation" is a foundational textbook in theoretical computer science that systematically develops the theory of automata, formal languages, and computational complexity.
All labels observed (2)
| Label | Occurrences |
|---|---|
| "Introduction to Automata Theory, Languages, and Computation" canonical | 1 |
| Introduction to Automata Theory, Languages, and Computation | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T2866509 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: "Introduction to Automata Theory, Languages, and Computation" Context triple: [Princeton Mathematical Series, workIncluded, "Introduction to Automata Theory, Languages, and Computation"]
-
A.
Introduction to the Theory of Computation
Introduction to the Theory of Computation is a widely used textbook in theoretical computer science that covers formal languages, automata, computability, and complexity theory.
-
B.
Compilers: Principles, Techniques, and Tools
Compilers: Principles, Techniques, and Tools is a foundational computer science textbook that systematically covers the theory and practice of compiler design and implementation.
-
C.
Chomsky hierarchy
The Chomsky hierarchy is a classification of formal grammars into four types that correspond to increasing levels of generative power and computational complexity in formal language theory.
-
D.
Introduction to Algorithms
Introduction to Algorithms is a widely used, comprehensive textbook on algorithms and data structures, renowned for its rigorous yet accessible coverage of theoretical and practical topics in computer science.
-
E.
Computability and Unsolvability
Computability and Unsolvability is a classic 1958 textbook by Martin Davis that systematically develops the theory of computable functions and undecidable problems, helping to shape modern computability theory.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: "Introduction to Automata Theory, Languages, and Computation" Target entity description: "Introduction to Automata Theory, Languages, and Computation" is a foundational textbook in theoretical computer science that systematically develops the theory of automata, formal languages, and computational complexity.
-
A.
Introduction to the Theory of Computation
Introduction to the Theory of Computation is a widely used textbook in theoretical computer science that covers formal languages, automata, computability, and complexity theory.
-
B.
Compilers: Principles, Techniques, and Tools
Compilers: Principles, Techniques, and Tools is a foundational computer science textbook that systematically covers the theory and practice of compiler design and implementation.
-
C.
Chomsky hierarchy
The Chomsky hierarchy is a classification of formal grammars into four types that correspond to increasing levels of generative power and computational complexity in formal language theory.
-
D.
Introduction to Algorithms
Introduction to Algorithms is a widely used, comprehensive textbook on algorithms and data structures, renowned for its rigorous yet accessible coverage of theoretical and practical topics in computer science.
-
E.
Computability and Unsolvability
Computability and Unsolvability is a classic 1958 textbook by Martin Davis that systematically develops the theory of computable functions and undecidable problems, helping to shape modern computability theory.
- F. None of above. chosen
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
computer science book
ⓘ
textbook ⓘ theoretical computer science textbook ⓘ |
| academicDiscipline |
computer science
ⓘ
mathematics ⓘ |
| author |
Jeffrey D. Ullman
ⓘ
John E. Hopcroft ⓘ Rajeev Motwani ⓘ |
| countryOfPublication |
United States of America
ⓘ
surface form:
United States
|
| field |
automata theory
ⓘ
computational complexity theory ⓘ formal languages ⓘ theoretical computer science ⓘ |
| hasEdition |
first edition
ⓘ
second edition ⓘ third edition ⓘ |
| language | English ⓘ |
| notableFor |
integration of automata, languages, and complexity theory
ⓘ
systematic development of automata theory ⓘ |
| originalAuthor |
Jeffrey D. Ullman
ⓘ
John E. Hopcroft ⓘ |
| pedagogicalFeature |
end-of-chapter exercises
ⓘ
formal proofs ⓘ worked examples ⓘ |
| publisher | Addison-Wesley ⓘ |
| topic |
Chomsky hierarchy
ⓘ
NP-completeness ⓘ P versus NP problem ⓘ Turing machine ⓘ
surface form:
Turing machines
closure properties of languages ⓘ computability ⓘ computational complexity ⓘ context-free grammars ⓘ decidability ⓘ deterministic finite automata ⓘ finite automata ⓘ nondeterministic finite automata ⓘ pumping lemma for context-free languages ⓘ pumping lemma for regular languages ⓘ pushdown automata ⓘ reducibility ⓘ regular expressions ⓘ regular languages ⓘ space complexity ⓘ time complexity ⓘ undecidability ⓘ |
| use |
graduate teaching
ⓘ
self-study ⓘ undergraduate teaching ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: "Introduction to Automata Theory, Languages, and Computation" Description of subject: "Introduction to Automata Theory, Languages, and Computation" is a foundational textbook in theoretical computer science that systematically develops the theory of automata, formal languages, and computational complexity.
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
Princeton Mathematical Series
→
workIncluded
→
"Introduction to Automata Theory, Languages, and Computation"
ⓘ
this entity surface form:
Introduction to Automata Theory, Languages, and Computation