dc.contributor.author |
Calude, CS |
en |
dc.contributor.author |
Freivalds, R |
en |
dc.contributor.author |
Stephan, F |
en |
dc.date.accessioned |
2014-01-05T22:48:16Z |
en |
dc.date.available |
2014-01-05T22:48:16Z |
en |
dc.date.issued |
2013 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-441 (2013) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/21340 |
en |
dc.description.abstract |
Frequency computation was introduced by Rose [26]. Trakhtenbrot [27] proved the existence of a continuum of functions computable
by frequency Turing machines with frequency 1/2 . In contrast, every function computable by a frequency Turing machine with frequency exceeding
1/2 is recursive. Essentially similar results for finite automata and other
types of machines have been proved by Kinber [19] and Austinat, Diekert,
Hertrampf, Petersen [4].
In this paper we introduce the notion of frequency pushdown automaton.
Answering a question E. Shamir posed at LATA 2013, we prove
that there is a language which is 1/1 -recognizable but which is not 2/n -
recognizable (for any n) by deterministic frequency pushdown 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 |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. |
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 Frequency Pushdown 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 |