Invariance properties of RAMs and linear time
type: Item
instance of: scholarly article
title: Invariance properties of RAMs and linear time
zbMATH Open document ID: 0806.68036
DOI: 10.1007/BF01205055
author: Etienne Grandjean
published in: Computational Complexity
publication date: 1994-07-13T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 591237
zbMATH Keywords: Turing machine
zbMATH Keywords: complexity measure
zbMATH Keywords: robust RAM complexity classes
zbMATH Keywords: linear-time computability
MaRDI profile type: Publication
cites work: Q4091421
cites work: Fast probabilistic algorithms for Hamiltonian circuits and matchings
cites work: Time bounded random access machines
cites work: Space measures for storage modification machines
cites work: Q4385524
cites work: Q4058132
cites work: Real-Time Simulation of Multihead Tape Units
cites work: Universal quantifiers and time complexity of random access machines
cites work: First-order spectra with one variable
cites work: Q4281688
cites work: Q3826533
cites work: Q3862379
cites work: Fast Simulation of Turing Machines by Random Access Machines
cites work: Random access machines with multi-dimensional memories
cites work: Satisfiability Is Quasilinear Complete in NQL
cites work: Storage Modification Machines
cites work: A nonlinear lower bound for random-access machines under logarithmic cost
cites work: The problem of space invariance for sequential machines
cites work: Q4038687
full work available at URL: https://doi.org/10.1007/bf01205055
OpenAlex ID: W2038232488
Recommended article: Determinism versus nondeterminism for linear time RAMs with memory restrictions
Recommended article: Determinism versus non-determinism for linear time RAMs (extended abstract)
Recommended article: Q4520496
Recommended article: The Density of Linear-Time Properties
Recommended article: Incompleteness in linear time
Recommended article: Lower Bounds for the Complexity of Functions in a Realistic RAM Model
Recommended article: Stubborn Sets for Simple Linear Time Properties
Recommended article: A characterization of alternating log time by ramified recurrence
Recommended article: LINEAR TIME IN HYPERSEQUENT FRAMEWORK
Recommended article: Lower bounds for dynamic data structures on algebraic RAMs
description: scientific article; zbMATH DE number 591237