Nerve Nets, Omega-regular Languages, and Reo

In this talk we relate Reo to some fundamental results in computer science.

In 1951, S.C. Kleene detailed the construction of nerve nets, and characterized their behavior in terms of events occurring within a finite frame of time. He then proved that regular events are exactly the events generated by finite automata (where a finite automaton is defined as a generalization of nerve nets).[1]

Later, J.R. Büchi formalized the notion of events as a formula in a weak-second-order logic. He extended the notion of regularity to events occurring within an infinite frame of time. Büchi then presented similar analysis and synthesis arguments as in the Kleene's case of finite frame of time.[2]

We relate Reo to the results of Kleene and Büchi, and present some ideas for future work

[1] "Representation of events in nerve nets and finite automata", S.C.Kleene http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf [2] "Weak-second order arithmetic and finite automata", J.R. Büchi https://deepblue.lib.umich.edu/bitstream/handle/2027.42/3930/bab9796.0001.001.pdf

hosted by

social