Alphabetical satisfiability problem for trace equations

Authors

  • Luca Breveglieri

Abstract

It is known that the satisfiability problem for equations over free partially commutative monoids is decidable but computationally hard. In this paper we consider the satisfiability problem for equations over free partially commutative monoids under the constraint that the solution is a subset of the alphabet. We prove that this problem is NP-complete for quadratic equations and that its uniform version is NP-complete for linear equations.

Downloads

Download data is not yet available.

Downloads

Published

2009-01-01

How to Cite

Breveglieri, L. (2009). Alphabetical satisfiability problem for trace equations. Acta Cybernetica, 19(2), 479–497. Retrieved from https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3778

Issue

Section

Regular articles