Decision Problems in the Theory of Automata
E900194
"Decision Problems in the Theory of Automata" is the doctoral thesis of computer scientist Amir Pnueli, focusing on foundational questions about the solvability and complexity of problems related to automata theory.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Decision Problems in the Theory of Automata canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T11016081 — 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: Decision Problems in the Theory of Automata Context triple: [Amir Pnueli, doctoralThesisTitle, Decision Problems in the Theory of Automata]
-
A.
Finite Automata and Their Decision Problems
"Finite Automata and Their Decision Problems" is a landmark 1959 paper by Dana Scott and Michael Rabin that founded the modern theory of finite automata and formalized key decision problems in automata theory and computation.
-
B.
Elements of the Theory of Computation
Elements of the Theory of Computation is a foundational textbook that introduces the mathematical and theoretical principles underlying computer science, including automata, formal languages, and computability.
-
C.
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.
-
D.
Automata and Computability (textbook)
Automata and Computability is a widely used theoretical computer science textbook by Dexter Kozen that introduces formal languages, automata theory, and the foundations of computability.
-
E.
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.
- 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: Decision Problems in the Theory of Automata Target entity description: "Decision Problems in the Theory of Automata" is the doctoral thesis of computer scientist Amir Pnueli, focusing on foundational questions about the solvability and complexity of problems related to automata theory.
-
A.
Finite Automata and Their Decision Problems
"Finite Automata and Their Decision Problems" is a landmark 1959 paper by Dana Scott and Michael Rabin that founded the modern theory of finite automata and formalized key decision problems in automata theory and computation.
-
B.
Elements of the Theory of Computation
Elements of the Theory of Computation is a foundational textbook that introduces the mathematical and theoretical principles underlying computer science, including automata, formal languages, and computability.
-
C.
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.
-
D.
Automata and Computability (textbook)
Automata and Computability is a widely used theoretical computer science textbook by Dexter Kozen that introduces formal languages, automata theory, and the foundations of computability.
-
E.
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.
- F. None of above. chosen
Statements (25)
| Predicate | Object |
|---|---|
| instanceOf |
academic dissertation
ⓘ
computer science work ⓘ doctoral thesis ⓘ |
| academicDegree | PhD ⓘ |
| academicDiscipline | mathematical logic in computer science ⓘ |
| author | Amir Pnueli ⓘ |
| authorNationality | Israeli ⓘ |
| authorOccupation | computer scientist ⓘ |
| contributionType | theoretical foundations ⓘ |
| field |
automata theory
ⓘ
computer science ⓘ theoretical computer science ⓘ |
| focusesOn |
complexity of automata-related problems
ⓘ
decidability of problems about automata ⓘ foundational questions in automata theory ⓘ |
| hasAuthor | Amir Pnueli ⓘ |
| language | English ⓘ |
| relatedTo |
complexity theory
ⓘ
computability theory ⓘ finite automata ⓘ formal languages ⓘ |
| topic |
computational complexity
ⓘ
decision problems ⓘ solvability of automata problems ⓘ |
| workType | research thesis ⓘ |
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: Decision Problems in the Theory of Automata Description of subject: "Decision Problems in the Theory of Automata" is the doctoral thesis of computer scientist Amir Pnueli, focusing on foundational questions about the solvability and complexity of problems related to automata theory.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.