Complexity theory and the operational structure of algebraic programming systems

DOI10.1007/BF00264163zbMath0489.68005MaRDI QIDQ1166916

S. Singh

Publication date: 1982

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

operational semanticsgrowth functionalgebraic 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

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

Related Items

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