𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Finite nondeterministic automata: Simulation and minimality

✍ Scribed by Cristian S. Calude; Elena Calude; Bakhadyr Khoussainov

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
159 KB
Volume
242
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

Motivated by recent applications of ΓΏnite automata to theoretical physics, we study the minimization problem for nondeterministic automata (with outputs, but no initial states). We use Ehrenfeucht-Fra sse-like games to model automata responses and simulations. The minimal automaton is constructed and, in contrast with the classical case, proved to be unique up to an isomorphism. Finally, we investigate the partial ordering induced by automata simulations. For example, we prove that, with respect to this ordering, the class of deterministic automata forms an ideal in the class of all automata.

πŸ“œ SIMILAR VOLUMES

Deterministic automata simulation, unive
Deterministic automata simulation, universality and minimality
✍ Cristian Calude; Elena Calude; Bakhadyr Khoussainov πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 906 KB

Finite automata have been recently used as alternative, discrete models in theoretical physics. especially in problems related to the dichotomy between endophysical/intrinsic and exophysical/ extrinsic perception (see, for instance [3,6,. These studies deal with Moore experiments; the main result st

Translating Regular Expressions into Sma
Translating Regular Expressions into Small Ξ΅-Free Nondeterministic Finite Automata
✍ Juraj Hromkovič; Sebastian Seibert; Thomas Wilke πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 252 KB

We prove that every regular expression of size n can be converted into an equivalent nondeterministic =-free finite automaton (NFA) with O(n(log n) 2 ) transitions in time O(n 2 log n). The best previously known conversions result in NFAs of worst-case size 3(n 2 ). We complement our result by provi

Minimization algorithm of fuzzy finite a
Minimization algorithm of fuzzy finite automata
✍ Wei Cheng; Zhi-Wen Mo πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 232 KB

In this paper, a class of fuzzy ΓΏnite automata corresponding to the Mealy type of ordinary automata is formulated, and also two types of statewise equivalence relations are introduced. From the equivalence relations, a minimal form is deΓΏned and a minimization algorithm of the Mealy type of fuzzy ΓΏn