dc.contributor.author |
Calude, E |
en |
dc.contributor.author |
Lipponen, M |
en |
dc.date.accessioned |
2009-04-16T23:17:09Z |
en |
dc.date.available |
2009-04-16T23:17:09Z |
en |
dc.date.issued |
1997-06 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-040 (1997) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3549 |
en |
dc.description.abstract |
We study finite deterministic incomplete automata without initial states. This means that
at any stage of a computation there is at most one transition to the next state. We will first investigate how two incomplete automata can simulate each other. Further on we construct an incomplete automaton which simulates a given automaton S and has the minimum
number of states compared to any other automaton simulating S. Finally, we study Moore's
uncertainty principles for incomplete automata. In contrast with the case of complete automata, it is possible to construct incomplete three-state automata displaying both types of
complementarity. |
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 |
Deterministic Incomplete Automata: Simulation, Universality and Complementarity |
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 |