Can I read A finite set of functions with an EXPTIME-complete composition problem on EtoBox?

A finite set of functions with an EXPTIME-complete composition problem by Marcin Kozik is a scholarly article available to read on EtoBox.

What is A finite set of functions with an EXPTIME-complete composition problem about?

We exhibit a finite family of functions over a finite set (i.e. a finite algebra), such that the problem whether a given function can be obtained as a composition of the members of this family (i.e. is a member of the clone generated by the algebra) is EXPTIME-complete.

Author

Marcin Kozik

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)

Published

2008

Language

EN