article

Free access

On Effective Procedures for Speeding Up Algorithms

Author:

Manuel BlumAuthors Info & Claims

Journal of the ACM (JACM), Volume 18, Issue 2

Pages 290 - 305

https://doi.org/10.1145/321637.321648

Published: 01 April 1971 Publication History

PDF eReader

References

[1]

HARTMANIS, J., AND STEARNS, R.E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 5 (May 1965), 285-306.

Google Scholar

[2]

BLUM, M. A machine-independent theory of the complexity of recursive functions. J. ACM 14, 2 (Apr. 1967), 322-336.

Crossref

Google Scholar

[3]

MEYER, A. R., AND FISCHER, P.C. On computational speedup. IEEE Conference Record Ninth Annual Symposium on Switching and Automata Theory (Oct. 1968), 351-355.

Google Scholar

[4]

YOUNG, P.R. Speed-ups by changing the order in which sets are enumerated. ACM Symposium on Theory of Computing, (May 1969), 89-92.

Crossref

Google Scholar

[5]

ROGERS, H., JR. G6del numberings of partial recursive functions. J. Symb. Logic 23, 3 (Sept. 1958), 331-341.

Google Scholar

[6]

ROGERS, H., JR. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.

Crossref

Google Scholar

[7]

YOUNG, P. R., AND HELM, J. P. On the size and efficiency of programs. Research Rep. CDS TR43, Dep. of Computer Science, Purdue U., Lafayette, Ind. (1969).

Google Scholar

[8]

RITCHIE, D.M. Program structure and computational complexity. Ph.D. Thesis, Dep. of Math. Harvard U., Cambridge, Mass. (1968).

Google Scholar

[9]

YOUNG, P.R. Toward a theory of enumerations. IEEE Conference Record Ninth Annual Symposium on Switching and Automata Theory (Oct. 1968), 334--350.

Google Scholar

Cited By

View all

Baldan PRanzato FZhang L(2022)Intensional Kleene and Rice theorems for abstract program semanticsInformation and Computation10.1016/j.ic.2022.104953289(104953)Online publication date: Nov-2022
https://doi.org/10.1016/j.ic.2022.104953
Bienvenu LDowney R(2019)On low for speed oraclesJournal of Computer and System Sciences10.1016/j.jcss.2019.08.007Online publication date: Sep-2019
https://doi.org/10.1016/j.jcss.2019.08.007
Asperti ALeroy XTiu A(2015)The Speedup Theorem in a Primitive Recursive FrameworkProceedings of the 2015 Conference on Certified Programs and Proofs10.1145/2676724.2693178(175-182)Online publication date: 13-Jan-2015
https://dl.acm.org/doi/10.1145/2676724.2693178
Show More Cited By

Index Terms

On Effective Procedures for Speeding Up Algorithms
1. Mathematics of computing
  1. Mathematical software
2. Theory of computation
  1. Models of computation
    1. Computability
      1. Turing machines

Recommendations

An effective method to obtain commutation positions in BLDC drive mode

The widely adopted drive method for the spindle motors with sinusoidal back-EMF in hard disk drive is to inject current into two phases and use the third phase to detect the rotor position. The commutation position to switch phases is normally 30 ...
Modeling, Simulation and Hardware Implementation of an Effective Induction Motor Controller
ICCMS '09: Proceedings of the 2009 International Conference on Computer Modeling and Simulation

This paper presents the modeling, simulation and hardware implementation of voltage/frequency control of induction motor which is the most widely used in industrial applications. In this paper, the voltage/frequency (V/Hz) control principle is used to ...
Effective Induction Motor Controller Based Voltage/Frequency
ICECT '09: Proceedings of the 2009 International Conference on Electronic Computer Technology

An effective scheme of induction motor control without using stator sensor is proposed in this paper. The effective scheme consist of speed calculation algorithm and voltage/frequency control. The speed calculation algorithm is achieved by sensoring the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 18, Issue 2

April 1971

192 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321637

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1971

Published in JACM Volume 18, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
538
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)7

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Baldan PRanzato FZhang L(2022)Intensional Kleene and Rice theorems for abstract program semanticsInformation and Computation10.1016/j.ic.2022.104953289(104953)Online publication date: Nov-2022
https://doi.org/10.1016/j.ic.2022.104953
Bienvenu LDowney R(2019)On low for speed oraclesJournal of Computer and System Sciences10.1016/j.jcss.2019.08.007Online publication date: Sep-2019
https://doi.org/10.1016/j.jcss.2019.08.007
Asperti ALeroy XTiu A(2015)The Speedup Theorem in a Primitive Recursive FrameworkProceedings of the 2015 Conference on Certified Programs and Proofs10.1145/2676724.2693178(175-182)Online publication date: 13-Jan-2015
https://dl.acm.org/doi/10.1145/2676724.2693178
Jahn M(2014)Implicit measurements of dynamic complexity properties and splittings of speedable setsThe Journal of Symbolic Logic10.2307/258661864:03(1037-1064)Online publication date: 12-Mar-2014
https://doi.org/10.2307/2586618
Stockmeyer L(2014)Classifying the computational complexity of problemsThe Journal of Symbolic Logic10.2307/227385852:1(1-43)Online publication date: 12-Mar-2014
https://doi.org/10.2307/2273858
Schnorr CFuchs P(2014)General random sequences and learnable sequencesThe Journal of Symbolic Logic10.2307/227286242:03(329-340)Online publication date: 12-Mar-2014
https://doi.org/10.2307/2272862
Meyer AFischer P(2014)Computational speed-up by effective operatorsThe Journal of Symbolic Logic10.2307/227254537:01(55-68)Online publication date: 12-Mar-2014
https://doi.org/10.2307/2272545
Blum MMarques I(2014)On complexity properties of recursively enumerable setsThe Journal of Symbolic Logic10.2307/227198438:04(579-593)Online publication date: 12-Mar-2014
https://doi.org/10.2307/2271984
Soare R(2014)Computational complexity, speedable and levelable setsThe Journal of Symbolic Logic10.2307/227187642:04(545-563)Online publication date: 12-Mar-2014
https://doi.org/10.2307/2271876
Zenil HSoler-Toscano FJoosten J(2012)Empirical Encounters with Computational Irreducibility and UnpredictabilityMinds and Machines10.1007/s11023-011-9262-y22:3(149-165)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1007/s11023-011-9262-y
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

An effective method to obtain commutation positions in BLDC drive mode

Modeling, Simulation and Hardware Implementation of an Effective Induction Motor Controller

Effective Induction Motor Controller Based Voltage/Frequency

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations