zbMATH — the first resource for mathematics

On the complexity of the solution of the problem of \(\alpha\)- expressibility in k-valued logic. (Russian) Zbl 0733.03015
Author’s summary: “The algorithmic complexity of the problem of recognition of determining whether a k-valued logic function belongs to the closure of a function system is investigated. The concept of \(\alpha\)-closure arises in finite automata theory; the concept is a specialization of the usual concept of closure. For \(k=2\), an essential difference of the lattice of \(\alpha\)-closed classes from the familiar lattice of closed classes is shown. This difference allows to construct an effective algorithm solving the problem in question without deeper investigations of the lattice of \(\alpha\)-closed classes in \(P_ 2\). It is proved that the problem in question is NP-hard when \(k>2.\)”
03B50 Many-valued logic
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata