• Maximal universal width of an...

Treffer: Maximal universal width of an AFA is NP-hard.

Title:
Maximal universal width of an AFA is NP-hard.
Authors:
Alajaji, John1 (AUTHOR) 18ja19@queensu.ca, Salomaa, Kai1 (AUTHOR) salomaa@queensu.ca
Source:
Theoretical Computer Science. Aug2025, Vol. 1045, pN.PAG-N.PAG. 1p.
Subject Terms:
*POLYNOMIAL time algorithms, *NP-hard problems, *ROBOTS, *INTEGERS, *DECISION making
Database:
Academic Search Index

Weitere Informationen

The maximal universal width of an alternating finite automaton (AFA) is the largest number parallel computations the machine can have. It is known that deciding finiteness of maximal universal width can be done in polynomial time. We show that deciding whether the maximal universal width of an AFA is greater than a given integer is NP-hard. The proof uses a reduction from the NP-hard membership problem of tabled 0L systems (J. van Leeuwen, 1975). [ABSTRACT FROM AUTHOR]