The Post correspondence problem over a unary alphabet
type: Item
instance of: scholarly article
title: The Post correspondence problem over a unary alphabet
zbMATH Open document ID: 1041.03031
DOI: 10.1016/S0893-9659(03)00073-9
author: Gerhard J. Woeginger
author: Piotr Rudnicki
published in: Applied Mathematics Letters
publication date: 2004-06-11T00:00:00Z
Mathematics Subject Classification ID: 03D03
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 2073732
zbMATH Keywords: Post correspondence problem
zbMATH Keywords: computational complexity
zbMATH Keywords: NP-completeness
zbMATH Keywords: pseudopolynomial time algorithm
MaRDI profile type: Publication
cites work: A variant of a recursively unsolvable problem
cites work: The (generalized) Post correspondence problem with lists consisting of two words is decidable
cites work: Q4198056
cites work: Q4536690
full work available at URL: s0893-9659(03)00073-9
OpenAlex ID: W2081149247
description: scientific article; zbMATH DE number 2073732