Complexity theory and the operational structure of algebraic programming systems

DOI10.1007/BF00264163MaRDI QIDQ1166916zbMATH OpenFDO

Authors S. Singh

Publication date 1982

Published in Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

growth functionoperational semanticsalgebraic data typeterm algebraclassification of programming systemsdeterministic and nondeterministic control constructs and assignmentsdeterministic polynomial space bounded computationsnondeterministic polynomial space bounded computationspolynomial space enumerable data typespolynomial time bounded computationpolynomial time implementable data typesspace and time resourcesspeed of growth of a data type

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Specification and verification (program logics, model checking, etc.) (68Q60)

Cited in

(4)

• Computation over algebraic structures and a classification of undecidable problems
• Effective constructions in well-partially-ordered free monoids
• Abstract grammars based on transductions
• Iterating iterated substitution

This page was built for publication: Complexity theory and the operational structure of algebraic programming systems

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