Space complexity in on-line computation

DOI10.1016/0022-0000(82)90032-0MaRDI QIDQ1167539zbMATH OpenOpenAlexFDO

Authors Hajime Machida, Takumi Kasai

Publication date 1982

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(82)90032-0

zbMATH Keywords

integer multiplicationlinear spaceobject code generationon-line Turing machinerecognition of powers of 3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites work

• A Remark on Acceptable Sets of Numbers
• Fast on-line integer multiplication
• scientific article; zbMATH DE number 3471609 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• On the Recognition of Primes by Automata
• Recognition time of context-free languages by on-line Turing machines
• Two memory bounds for the recognition of primes by automata

Cited in

(1)

• A survey of space complexity

This page was built for publication: Space complexity in on-line computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1167539)