DocumentCode :
1446742
Title :
On-the-Fly Algorithms and Sequential Machines
Author :
Pippenger, Nicholas
Author_Institution :
Dept. of Math., Harvey Mudd Coll., Claremont, CA, USA
Volume :
60
Issue :
9
fYear :
2011
Firstpage :
1372
Lastpage :
1375
Abstract :
Frougny has presented a method that generalizes various "on-the-fly” operations that have been presented, mainly in connection with computer arithmetic. First, we shall trace the origin of this method to its source, which is the celebrated paper of Rabin and Scott that introduced the notion of nondeterminism and the power-set construction. Second, we shall show that an understanding of this origin may lead to great quantitative improvements in applications of the method. Finally, we shall show by a pathological example that the method as originally presented by Frougny may result in circuits that are larger, in terms of gates per step, by two exponentiations than those that are constructed as described in the present paper.
Keywords :
digital arithmetic; sequential machines; Frougny; computer arithmetic; on-the-fly algorithms; power-set construction; sequential machines; Automata; Delay; Digital arithmetic; Logic gates; Multiplexing; Registers; Transducers; Finite automata; regular language; reversal.;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/TC.2011.35
Filename :
5710885
Link To Document :
بازگشت