𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The size of power automata

✍ Scribed by K. Sutner

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
179 KB
Volume
295
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We describe a class of simple transitive semiautomata that exhibit full exponential blow-up during deterministic simulation. For arbitrary semiautomata we show that it is PSPACE-complete to decide whether the size of the accessible part of their power automata exceeds a given bound. We comment on the application of these results to the study of cellular automata.

πŸ“œ SIMILAR VOLUMES

On the computational power of pushdown a
On the computational power of pushdown automata
✍ A.V. Aho; J.D. Ullman; J.E. Hopcroft πŸ“‚ Article πŸ“… 1970 πŸ› Elsevier Science 🌐 English βš– 361 KB

We present a relation between the sets accepted by two-way pushdown automata and certain tape complexity classes of off-line Turing machines. Specifically, let L be a language accepted by a nondeterministic off-line Turing machine T. Let T have a t-symbol storage-tape alphabet. If for all but a fini

The power of reachability testing for ti
The power of reachability testing for timed automata
✍ Luca Aceto; Patricia Bouyer; Augusto BurgueΓ±o; Kim G Larsen πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 824 KB

The computational engine of the veriΓΏcation tool UPPAAL consists of a collection of e cient algorithms for the analysis of reachability properties of systems. Model-checking of properties other than plain reachability ones may currently be carried out in such a tool as follows. Given a property to m