Simple programming languages and restricted classes of Turing machines

DOI10.1016/0304-3975(83)90085-3MaRDI QIDQ792760zbMATH OpenOpenAlexFDO

Authors 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

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Recommendations

• Computer Science Logic
• On the computational complexity of imperative programming languages
• LOGSPACE and PTIME characterized by programming languages
• SAFE TURING MACHINES, GRZEGORCZYK CLASSES AND POLYTIME
• On simple programs with primitive conditional statements

Cites work

• scientific article; zbMATH DE number 3817043 (Why is no real title available?)
• scientific article; zbMATH DE number 3592964 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• A Complete and Consistent Hoare Axiomatics for a Simple Programming Language
• A characterization of time complexity by simple loop programs
• Counter machines and counter languages
• Loop-programs and polynomially computable functions
• Predecessor machines
• Simple Programs Realize Exactly Presburger Formulas
• The Complexity of the Equivalence Problem for Simple Programs
• The Equivalence Problem of Simple Programs

Cited in

(9)

• A language for easy and efficient modeling of Turing machines
• A note on simple programs with two variables
• On the computational complexity of imperative programming languages
• Machines, Computations, and Universality
• scientific article; zbMATH DE number 3900134 (Why is no real title available?)
• scientific article; zbMATH DE number 3995054 (Why is no real title available?)
• On simple programs with primitive conditional statements
• A note on the complexity of program evaluation
• Computer Science Logic

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

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