Computational memory of this type of model is fixed. In particular, the class of problems this type of automata solves (“languages it recognizes”) is called regular languages.

We want to explore the closure properties of regular languages (does combining regular languages result in regular languages)

constituents

A DFA is a five-tuple \(M = (Q, \Sigma, \delta, q_{0}, F)\).

• \(Q\): finite set of all states
• \(\Sigma\): the alphabet
• \(\delta: Q \times \Sigma \to Q\), the transition function
• \(q_0 \in Q\): the start state
• \(F \subseteq Q\): the accept states, which means we accept the input string we got if after processing the string we ended up at one of these states

requirements

if processing an input results in an accepting state, we accept the input; otherwise, we reject the input. this is the computation.

key idea: let’s build a tree such that, after taking the action, the observation is deterministic. Therefore, you get a belief tree with no branching on observations.

DESPOT trees

We make an assumption, that the actual observation given are fixed given belief. That is:

\begin{equation} O(o|b,a) = 1 \end{equation}

for some specific \(o\), everything else is \(0\) for every b,a.

Sample Scenarios

To make such a tree, let’s sample of set of scenarios: sequences of actions and observations (because, given a belief and action, we assume observation is fixed. So, given an initial belief and an action, you will always go down a single “scenario”).

A health concern relating to glucose and obesity.

The diagonal of a square matrix consists of entries from the upper-left to the bottom-right

Furthermore, because eigenvalues of a map are the entries of the diagonal of its upper-triangular matrix, and this is technically an upper-triangular matrix, the entries on the diagonal are exactly the eigenvalues of the Linear Map.

properties of diagonal matrices

Suppose \(V\) is finite-dimensional, and \(T \in \mathcal{L}(V)\); and let \(\lambda_{1}, … \lambda_{m}\) be distinct eigenvalues of \(T\). Then, the following are equivalent:

see Diagonalization Arguments