TU/e EE Notes

Computation Modeling - 5XIE0

17 min read

5XIE0 Computation Modeling

Module A: Languages and Automata, Property Checking

Week 1: A.1 & A.2

Formal Languages A.1

Kleene star - Wikipedia
precise means of specifying patterns/behaviors



accumulation of amounts of a, for each a we do +2 so if aba→ 4.

example:
is the language of all numbers in which every 0 is eventually followed by a 1






Regular Languages A.2.1

class of language specified by regular expressions

powers: repetition where .
concatenation: put words together.




unary operator

operations on languages: regular expressions define languages.
concatenation: combining strings of two languages to form a language.
interaction: find common elements between languages.

empty word, you can perform concatenations on which would result in the other. cant concatenate empty language like multiplying by zero.





is not the same since




((as long as repetition of ends with 1 (concatenated)) that can be repeated) and that ends with any repetition of (concatenated) ensuring does not end with 0.

regular expression cant keep track of more than 1 count.
for counting amount of amount of 1s making sure its even: .

Finite Automata A.2.2

Topic: Finite State Machines and Automata
Regular Languages: Deterministic Finite Automaton (DFA)
Regular Languages: Nondeterministic Finite Automaton (NFA)

word/string is element of language if A from init to final state labeled with that word.

left: DFA so is NFA, right: none



dfa,nfa,nfa- all define precisely the class of regular languages.

examples



a3 in picture above look at it as if it reuses a*
and thats why the image on the right shows that repetition logic

Conversions Between Representations of Regular Languages A.2.4

A Quick Non-Deterministic to Deterministic Finite Automata Conversion - YouTube
Best conversion example

Deterministic Finite Automata (Example 3) - YouTube
revert a state machine DFA → flip final states to none final and vice versa

conversions between regular expressions, DFA, NFA, NFA-
conversion between expressions and NFA-, NFA is subset of NFA- and DFA is subset of NFA.



basically repeat until only initial and final state remain

Expressiveness A.2.3

What is the Pumping Lemma - YouTube
Nonregular languages: How to use the Pumping Lemma - YouTube
Pumping lemma for regular languages - Wikipedia
What Is the Pigeonhole Principle? - YouTube


any complete DFA can be complemented to by swapping final and non-final states

Best example for pumping lemma: Pumping Lemma (For Regular Languages) | Example 1 - YouTube

infinite many options is impossible in regular languages.
pumping lemma: some section of a language can be repeated still keeping the language regular. (pumping lemma can prove is language is NOT REGULAR)
string in language can be “pumped” repeated if they are at least as long as pumping length p.

pumping: have a middle section of the string repeated an arbitrary number of times

for example:pumping the repeated words still keeps string in the language

  • so we can split strings into parts before being pumped, being pumped and part that takes us to final state.

    y can be pumped any number of times, y must be bigger than 0 (not ), cant pump words bigger than p

pigeon hole principle: if objects are put in boxes with , then at least one box contains multiple objects


So, if a language contains infinitely many words that need to be distinguished, this cannot be done with finitely many states. In such a case, using the pigeonhole principle, no finite automaton recognizing the language exists. So the language is not regular.

Week 2: A.3 & A.4

Property Checking A.3


computing language interaction product automation: think of matrix dot product.



complement → invert normal states to final states and final states to normal states.
use logic to the determine the fact that final system is empty language, the one below is not empty since it has final states so does not satisfy

must not have final states…

-Regular Languages A.4.1

Omega-regular language - Wikipedia
Omega language - Wikipedia

  • a set of infinite words over some alphabet .
  • one infinite word abstracts infinitely many finite behaviors.
  • useful when behavior is unbounded.


    -regular expressions pattern:
    legend: regular expressions

    the * is all finite repetitions, while infinite repetitions, they are complementary.

Büchi Automata A.4.2

Topic: Finite State Machines and Automata
Büchi automaton - Wikipedia

either accepts or rejects some infinite inputs:

  • indefinite automata…
  • Büchi automaton is an NFA but with different acceptance conditions
  • -regular expressions and NB(Buchi)A both define precisely the class of -regular languages


    infinity happens in finite states…
    complete means all symbols used…

    ending on a different final state makes a difference as shown above…

Week 3: A.4

Expressiveness A.4.3 & A.4.4

DBA: deterministic Buchi Automaton.
an -language is deterministically Büchi‐recognizable if and only if there is a DBA accepting the language.

since is not deterministically Büchi-recognizable.
expressiveness of DBA:

  • DBA are strictly less expressive than NBA
  • deterministically Büchi-recognizable languages are not closed under development


    The above proves that DBA can only exists if there is limit of a regular language…

class of -regular languages is closed under complement and hence under intersection

non-regular -languages are possible



we can see that if languages are each others complements in infinite context IT DOESNT imply they are in finite context

!!! unbounded chain of finite words converges to an infinity allowing to say that , this is always true for deterministic but not always true for non-deterministic automata.

Conversions A.4.5

similar to finite word language conversions…
split into 3 parts, make sure they are epsilon included, and then start elimination.




pattern

Property Checking A.4.7

  • similar to finite language property checking…
  • emptiness of a regular language can be checked by checking  for the reachability of a final state in an automaton.
  • But emptiness of an ω‐regular language can be checked by a  nested depth‐first search on the automaton checking for the reachability of a final state and a cycle back to that final state.
  • but complement of ω‐regular languages is not practical.


    a GNBA is an NBA but with multiple sets of final states…
    GNBA vs NBA:


empty language means that there is at least one state which is not visited infinite amount of times…

Week 4: A.5

Logic and Property Checking A.5.1 & A.5.3



propositions over an alphabet of symbols

  • atomic propositions Π are sets of symbols from Σ characterizing those symbols that satisfy the proposition


Module B: Markov Modeling, Discrete-Event Simulation

Week 4: B.1 & B.2 & B.3

Discrete-time Stochastic Processes B.1

Topic: Probability and Random Variables

  • random state of a system at time
  • finite set of states, state-space
  • probability that system in state at time where realization of
  • probability distribution of
  • reward and random variable denotes reward that is earned at time
  • set of possible realization of
  • probability reward earned at
  • expected reward earned at and is row vector also
    sum of all values that can occur, of the value that occurs, times the probability that that value occurs. Expected value probability…

Markov Chains B.2

Topic: Probability and Random Variables


identically distributed

for all and → (pairwise) independent iff

markov chain is time homogeneous


Transient Analysis B.3

  • law of total probability:
  • So distribution vector:

Transition Probability of Something Occurring:

  • n-step transition probability from i to j:
  • sum of probabilities of paths:
    • sum of probabilities of all paths from to of length
    • path is a sequence of states
    • number of transitions made

      (row(i) 3 column(j) 4) = 0.667


Week 5: B.4 & B.5 & B.6

State Classification B.4



  • means start at and return to

  • recurrent iff infinitely returns in one or more steps

  • transient iff eventually won’t be visited

  • both are class properties also could be closed

  • periodic if visited not visited

  • aperiodic always visited from time

  • also class properties

  • aperiodic class and all states →

if recurrent state with a self loop then → aperiodic otherwise periodic

  • ergodic recurrent & aperiodic
  • unichain single recurrent & zero or more transient

Hitting Probabilities B.5

  • hit probability that state ever visited starting
  • system of linear of equations as solution

probability-weighted average of cumulative rewards
expected cumulative reward until state is hit starting from

set of states:
probability to hit a set of states
is expected cumulative reward until state set is hit, starting from

Long-run Analysis B.6

  • converge in distribution: ergodic unichain

  • balance equation which have stationary solution which exist iff chain is unichain


  • We can see that first 2 are transient and are zero in long run… 4 units in markov chain average reward…

  • non-ergodic unichain those limits dont exist, still has a unique stationary solution: cezaro limit

  • cezaro limit: long-run expected fraction of time the chain spends in state

  • long-run expected fraction of time the chains spends in state , given that it started in

  • each row

  • long run expected average reward


Week 6: B.7

Discrete-event Simulation B.7

Discrete-event simulation - Wikipedia

estimaiton theory

identically distributed independent random variable.
.

goal: estimate based on simulation sequence of length .
approach: estimate by

errors

absolute estimation error
relative estimation error

How big M(simulation sequence so acceptable error):

standard deviation and point estimator are equivalent when



also called the confidence interval…
success confidence bound
relative success confidence bound if doesn’t contain

negative values


Transient Markov application

markov chain application - transient properties:

long-run properties


point estimation, interval estimation, generate estimation

based on strong law of large numbers

converges
converges

based on central limit theorem


exercises

 Module C: Dataflow, Max-Plus Linear Systems, Performance Analysis

Module C Slides

Week 6: C.1 & C.2 & C.3

C.1 Timed Dataflow Models

MULTI RATE DATAFLOW CHART OUTSIDE OF SCOPE (CAN BE DESCRIBED IN VECTOR) can be converted to single rate

  • finite set of actors
  • firing durations (time units)
  • finite set of channels
  • finite set of inputs with input dependencies
  • finite set of outputs with output dependencies

  • BT actor models the transport of the top on the belt to the pick-and-place unit, where it is combined with a bottom.
  • BB models its transport to the indexing table.
  • initial token on the cycle ensures that the first object admitted is a top.
  • initial token on the channel from Rot to PaP represents the bottom part that is initially placed in the system.
  • dependency from PaP to Rot ensures that the indexing table does not rotate until the pick-and-place operation is complete.


multi token production :

Given the input sequence and the duration of the Sh actor, the decoder cannot decode symbols faster than 1 symbol per 4 time units. With two tokens on the channel from CE to DM, it operates at this maximum rate; with only one token, it does not. So the most recent channel-estimation information that DM can use is two symbols old.

  • to have synchronous operation one after the other the actor should have a self referencing channel dependency with a token.
  • hot to determine maximal operation: squash the synchronous operation time units as close as possible and then determine the tokens required for that
  • 2 units at A trigger I
  • 4 units at A to trigger I

How to ensure order of operation:

F1 fires first in this case.

Reducing the number of processors:

C.2 Schedules & Performance

schedule partial function: that assigns starting times to the firings of actors of , such that is the starting time of firing number of actor .

schedule is for given input arrivals iff satisfies channel and input constraints:

  • self-timed schedule: as soon as possible asap
  • as late as possible alap
  • complete all actor firings assigned starting time
  • periodic
  • finite if
  • live if is defined for infinitely many for all actors
  • example above: periodic:

Throughput intuitively refers to the amount of processing that a system can perform, on average, in the long run, per unit of time. It is relevant for indefinite operation. Makespan, in contrast, is a performance metric that can be associated with finite behaviors. It refers to the total amount of time that it takes to complete a job. Finally, latency is a metric that characterizes the time span between the start and the completion of the processing of individual elements.

non periodic throughput example:

Actor C fires 2 times per 5 time units, so the throughput is 

C.3 Max-plus Algebra

time stamp os value from set and set of time stamps:

  • compute time stamp:
  • assume self-timed firing of with 2 inputs:

Week 7: C.4 & C.5 & C.6 & C.7 & C.8

C.4 Max-plus-linear Systems

event sequence:
note event sequence does not require order:




we operate always with index invariant systems since we have single rate dataflows…

superposition

  • a linear system has the superposition property
  • if a complex stimulus (input) can be described as the maximum (⊕, superposition) of two or more simpler stimuli, then
    • analyze the responses to the simpler stimuli separately
    • determine the superposition (max) of the separate responses
  • divide-and-conquer strategy
    • typically among different inputs of the system

C.5 Impulse Response

  • impulse sequence: is an event sequence such that and for
  • impulse response: of event system is the event sequence such that and multiple inputs and/or outputs
  • an impulse is the smallest part of an event sequence
  • every event sequence is the maximum of scaled and delayed impulses
  • linear and index-invariant event systems are completely characterized by their impulse response


If is a max-plus-linear and index-invariant system with impulse response , then for any input event sequence

C.6 Max-plus Linear Algebra

Topic: Linear Algebra



C.7 From Dataflow to Max-plus



C.8 Monotonicity

Monotonic function - Wikipedia
max-plus algebra is monotone
if
if

ordering event sequences:
convolution is monotone: if are event sequences such that and then

Week 8: C.9 & C.10 & C.11 & C.12

C.9 The Eigenvalue Equation

Topic: Linear Algebra




  • precedence graph take the longest channel length: example for




normalized eigenvector:
max(0, 4, -1) = 4 [0-4, 4-4, -1-4] = [-4, 0, -5]

  • eigenvector for the largest eigenvalue can be constructed using the precedence graph
  • choose one of the puncts for the eigenvector and then choose its longest paths to the other puncts

example



eigenvalue and normalized eigenvector obtained:


c is 6 to make it non negative:
starting at 2 because it receives tokens from

C.10 State Space Equations

Topic: State-Space Models





C.11 Throughput


maximal throughput of max-plus-linear system on output is
where
the throughput of a max-plus-linear system is

example: 1 time unit delay per box; 5 time units to reach the end of the belt: so output: so the maximal throughput:

max-plus-linear system with state matrix with largest eigenvalue
if for every element of the state vector there is an output that depends on it, then the maximal throughput of is

max-plus linear system with matrix with largest eigenvalue and has input sequence have respective average rates of then the average rate of the output sequence is

self-timed throughput: let matrices be state-space representations of timed dataflow graph . Let have largest eigenvalue . Then max throughput of is . If provided with input event sequence with rates then throughput of self-timed execution

C.12 Latency




observing from graph the latency: row 1 eg:

best to do latency mathematically:

max-plus-linear algebra operations are monotone:
The ∗-closure is monotone. I.e., let such that exists, then exists and

(EXCLUDED) C.13

Dataflow and Max-Plus Algebra

Edit this page on GitHub · History

Graph View

Backlinks