The R. E. Complexity of Decision Problems for Commutative Semi‐Thue Systems With Recursive Rule Set

DOI10.1002/MALQ.19800262805MaRDI QIDQ3964546zbMATHOpenAlexFDO

Authors Egon Börger, Hans Kleine Büning

Publication date 1980

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19800262805

zbMATH Keywords

word problemreachability problemhalting problemvector addition systemconfluence problem

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Thue and Post systems, etc. (03D03) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Word problems, etc. in computability and recursion theory (03D40)

This page was built for publication: The R. E. Complexity of Decision Problems for Commutative Semi‐Thue Systems With Recursive Rule Set

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