AGV 2.1 -- Büchi automata (Preliminaries)

Previous chapter: The Logic-Automata Connection

This is a learning note of a course in CISPA, UdS. Taught by Bernd Finkbeiner

2.1 Preliminaries

Basic math notations	Example
Natural numbers	$\mathbb{N} = \lbrace 0,1,2,3\dots\rbrace$
Positive Natural numbers	$\mathbb{N}^+ = \lbrace 1,2,3\dots\rbrace$
Numbers from $n$ to $m$	$[n,m] = \lbrace n,n+1,\dots,m\rbrace$ For $n,m\in \mathbb{N}$ with $n\leq m$
Numbers from $0$ to $m$	$[m] = \lbrace 0,1,\dots,m\rbrace$

$$$$

Alphabet and Letter	Example
Alphabet	a nonempty, finite set of symbols, usually denoted by $\Sigma$
Letter	elements of an alphabets, denoted by $\sigma$

$$$$

Finite and Infinite Word	Example
Finite Words	concatenation $w=w(0)w(1)\dots w(n-1)$ of finitely many letters of $\Sigma$
Infinite Words	$\alpha$ (will be explained in chapter 2.3
$n$-th letter of word $w$	$w(n)$ for each $n\in [|w| - 1]$
Length of words $w$	$|w|$
set of all finite words	\Sigma^*$
Infinite Words	$\alpha$ (will be explained in chapter 2.3
set of all non-empty finite words	$\Sigma^+ = \Sigma^* \backslash \lbrace \epsilon \rbrace$
set of all infinite words	$\Sigma^\omega$

$$$$

Language	Example
language over finite words ($\omega$-language)	each subset of $\Sigma^*$
language over infinite words ($\omega$-language)	each subset of $\Sigma^\omega$

---

Next chapter: Automata over Infinite Words

Further Reading: Büchi automaton, Omega language