dc.contributor.author |
Calude, C.S |
en |
dc.contributor.author |
Calude, E |
en |
dc.date.accessioned |
2009-04-16T23:16:04Z |
en |
dc.date.available |
2009-04-16T23:16:04Z |
en |
dc.date.issued |
1999-02 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-092 (1999) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3601 |
en |
dc.description.abstract |
The minimization of nondeterministic automata without initial states (developed
within a game-theoretic framework in Calude, Calude, Khoussainov [3]) is presented
in terms of bisimulations; the minimal automaton is unique up to an isomorphism
in case of reversible automata. We also prove that there exists an in nite class
of (strongly connected) nondeterministic automata each of which is not bisimilar
with any deterministic automaton. This shows that in the sense of bisimilarity
nondeterministic automata are more powerful than deterministic ones. It is an open
question whether the method of bisimulations can produced, in general, the unique
minimal nondeterministic automaton. |
en |
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
CDMTCS Research Report Series |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial |
en |
dc.title |
Bisimulations and Behaviour of Nondeterministic Automata |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research::280000 Information, Computing and Communication Sciences |
en |
dc.rights.holder |
The author(s) |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |