Oded Maler: Abstracts of Unpublished Manuscripts
O. Maler, A. Pnueli, On the Cascaede Decomposition of Automata,
its Complexity and Application to Logic. The primary decomposition
theorem due to Krohn and Rhodes ([KR65]), which is considered as one of
the fundamental results in the theory of automata and semigroups, states
that every automaton is homomorphic to a cascaded decomposition (wreath-product)
of simpler automata of two kinds: reset automata and permutation
automata. If the automaton is non-counting (and correspondingly its transformation
semigroup is group-free) then it can be decomposed using only reset components.
There exist various proofs and partial proofs for the primary decomposition
theorem e.g., [HS66, Ze67a, Ze67b, Gi68, MT69, La71, We76, Ei76]. None
of them give explicit bounds on the size of the decomposition. (To quote
the last paragraph in Ginzburg's book ([Gi68]): "Finally, notice
that the above theory does not indicate how many particular basic building
blocks are needed to construct a cascade product covering of a given semiautomaton.".
In this paper we give tight exponential bounds on the size of the decomposition.
For the upper-bound we give an exponential algorithm by modifying the implicit
construction appearing in [Ei74]. Based on this construction we give an
exponential upper-bound on transforming star-free regular (resp. omega-regular)
sets expressed by counter-free automata (resp. omega-automata) into past
(resp. future) temporal logic formulae. These upper bounds improve upon
previously-known non-elementary translations (MNP71, LPZ85, Zu86).
Our decomposition construction is proved to be optimal by showing the existence
of a family of automata such that the size of their minimal permutation-free
decomposition is exponential in the size of the automaton (by size we refer
to the total number of defined transitions). [Pdf]
(This is a draft).
O. Maler, Hybrid Systems and Real-World Computations. In this
non-technical note I will comment on the novel features that hybrid systems
research introduces into theoretical and practical computer science. I
will argue that classical notions of computability and complexity cannot
capture the phenomenon of embedded or real-world computations, and that
hybrid system models are a natural next step in the passage from static
to dynamic environments. [Pdf]
O. Maler, Why should we Develop Artificial Worms and How? In
this paper it is argued that a certain class of intelligent systems is
worth being investigated and developed. This class consists of elastic
robots composed of many components having relatively-simple sensory-motor
capabilities, whose most prominent biological realizations are worms, molluscs,
elephant trunks and tongues. Understanding how such mechanisms are controlled
is an important stage (not to say, a prerequisite) toward the development
of ``truely-intelligent'' autonomous agents. As a preliminary step in this
direction I describe a simple elastic object considered as a first approximation
of an artificial worm and discuss its control principles. [Pdf]