An NP-hardness Result on the Monoid Frobenius Problem

Simple item page
dc.creatorXu, Zhi
dc.creatorShallit, J.
dc.date2008-05-27
dc.date2008-06-30
dc.date.accessioned2026-07-07T09:47:05Z
dc.date.available2026-07-07T09:47:05Z
dc.descriptionThe following problem is NP-hard: given a regular expression $E$, decide if $E^*$ is not co-finite.
dc.description2 pages, working paper; an error in Problem 5 is corrected
dc.identifierhttps://arxiv.org/abs/0805.4049
dc.identifierhttp://arxiv.org/abs/0805.4049
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/163751
dc.subjectDiscrete Mathematics
dc.subjectComputational Complexity
dc.subjectF.2.2; G.2.1
dc.titleAn NP-hardness Result on the Monoid Frobenius Problem
dc.typetext

Files

Collections

arXiv