ICG Chapter 1 Introduction
Questions about the lecture 'Infinte computations and games' of the RWTH Aachen Chapter 1 Introduction
Questions about the lecture 'Infinte computations and games' of the RWTH Aachen Chapter 1 Introduction
20
0.0 (0)
R. B.
R. B.
This flashcard set introduces university-level computer science concepts related to formal languages and automata theory. It covers definitions and characteristics of Büchi automata, including non-deterministic and deterministic variants, their acceptance conditions, and recognizable languages. The set also explores historical developments, notations for infinite words, and motivations for studying infinite executions. Ideal for students and researchers, it provides a comprehensive overview of the theoretical foundations and practical applications in verification and synthesis.
Karten
20
Lernende
1
Sprache
Englisch
Kategorie
Informatik
Stufe
Universität
Erstellt / Aktualisiert
05.02.2017 / 13.10.2017
-
- 1 / 20
-
Lernkarten
What is the definition?
[rho.DBA.büchi, 2]
1. rho(0)=q0
2. rho(i+1)=delta(rho(i),alpha(i))
What is the definition?
[NBA.büchi, 4]
1. A=(Q,Sigma,q0,Delta,F) with Delta \subseteq Q x Simga x Q
2. Run on alpha in Sigmaomega is rho in Qomega
3. A accepts alpha is there is at least one accepting run of A on alpha
4. Language is defined as for DBA
What is the definition?
[rho.NBA.büchi, 2]
1. rho(0)=q0
2. (rho(i),alpha(i),rho(i+1)) in Delta
What is the definition?
[theorem.büchi]
The class of DBA recognizable languages is not closed under complement
