On the complexity of the correctness problem for non-zeroness test instruction sequences

DOI10.1016/J.TCS.2019.03.040zbMath1436.68079arXiv1805.05845OpenAlexW2803201015WikidataQ128140358 ScholiaQ128140358MaRDI QIDQ2007725

C. A. Middelburg, Jan A. Bergstra

Publication date: 22 November 2019

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

Full work available at URL: https://arxiv.org/abs/1805.05845

zbMATH Keywords

computational complexityinstruction sequencecorrectness problemnon-zeroness test

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Cites Work

• Unnamed Item
• Time bounded random access machines
• Program algebra for sequential code
• On Algorithmic Equivalence of Instruction Sequences for Computing Bit String Functions
• Complexity Theory
• Instruction Sequence Size Complexity of Parity
• Instruction Sequence Based Non-uniform Complexity Classes
• On Instruction Sets for Boolean Registers in Program Algebra
• Axioms for Behavioural Congruence of Single-Pass Instruction Sequences

This page was built for publication: On the complexity of the correctness problem for non-zeroness test instruction sequences