scientific article; zbMATH DE number 3986645

MaRDI QIDQ3750122zbMATH OpenFDO

Authors Giancarlo Mauri, Alberto Bertoni, N. Sabadini

Publication date 1985

zbMATH Keywords

counting problemcounting functiondivision RAMequivalence problem for straight line programs on integerssatisfiability of quantified Boolean formulassimulations among RAM's with powerful instructions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• Fast Simulation of Turing Machines by Random Access Machines
• On efficient simulations of multicounter machines
• Simulation of Parallel Random Access Machines by Circuits
• scientific article; zbMATH DE number 1396672
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• On approximating the ideal random access machine by physical machines
• Simulations by time-bounded counter machines
• Simulations by Time-Bounded Counter Machines
• On Efficient Simulations of Systolic Arrays by Random-Access Machines
• On efficient deterministic simulation of turing machine computations below logaspace

Cited in

(8)

• The problem of space invariance for sequential machines
• Parallel machine models: how they are and where are they going
• On Faster Integer Calculations Using Non-arithmetic Primitives
• Theory of Cryptography
• Squeezing Feasibility
• Sorting, linear time and the satisfiability problem
• Smoothing the Gap Between NP and ER
• Preface

This page was built for publication:

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