Simple programming languages and restricted classes of Turing machines

DOI10.1016/0304-3975(83)90085-3zbMath0537.68045OpenAlexW2009880057MaRDI QIDQ792760

Oscar H. Ibarra, Louis E. Rosier

Publication date: 1983

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90085-3

zbMATH Keywords

complexity classes of Turing machinescomputational power of simple programming languages

Mathematics Subject Classification ID

Related Items (1)

A note on the complexity of program evaluation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of time complexity by simple loop programs
• Predecessor machines
• Loop-programs and polynomially computable functions
• The Complexity of the Equivalence Problem for Simple Programs
• Simple Programs Realize Exactly Presburger Formulas
• A Complete and Consistent Hoare Axiomatics for a Simple Programming Language
• Counter machines and counter languages
• The Equivalence Problem of Simple Programs

This page was built for publication: Simple programming languages and restricted classes of Turing machines