On the complexity of the solution of the problem of \(\alpha\)- expressibility in k-valued logic. (Russian) Zbl 0733.03015

Emel’yanov, N. R.

Diskretn. Mat. 1, No. 2, 65-77 (1989).

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.\)”

Reviewer: A.Karpenko (Moskva)

MSC:

03B50	Many-valued logic
68Q25	Analysis of algorithms and problem complexity
68Q45	Formal languages and automata

Keywords:

algorithmic complexity; k-valued logic function; \(\alpha\)-closure; lattice of closed classes; effective algorithm