Invariance properties of RAMs and linear time

DOI10.1007/BF01205055zbMath0806.68036OpenAlexW2038232488MaRDI QIDQ1327595

Etienne Grandjean

Publication date: 13 July 1994

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01205055

zbMATH Keywords

Turing machinecomplexity measurelinear-time computabilityrobust RAM complexity classes

Mathematics Subject Classification ID

Related Items (6)

Algebraic and logical characterizations of deterministic linear time classes ⋮ Graph properties checkable in linear time in the number of vertices ⋮ A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES ⋮ Sorting, linear time and the satisfiability problem ⋮ Linear time and the power of one first-order universal quantifier ⋮ On the expressive power of monadic least fixed point logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-order spectra with one variable
• Random access machines with multi-dimensional memories
• The problem of space invariance for sequential machines
• Space measures for storage modification machines
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Time bounded random access machines
• Universal quantifiers and time complexity of random access machines
• Fast Simulation of Turing Machines by Random Access Machines
• A nonlinear lower bound for random-access machines under logarithmic cost
• Storage Modification Machines
• Satisfiability Is Quasilinear Complete in NQL
• Real-Time Simulation of Multihead Tape Units

This page was built for publication: Invariance properties of RAMs and linear time