Pseudo-free families of computational universal algebrasстатьяЭлектронная публикация
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 января 2021 г.
Аннотация:Let Ω be a finite set of finitary operation symbols. We initiate the study of (weakly) pseudo-free families of computational Ω-algebras in arbitrary varieties of Ω-algebras. A family (H_d|d∈D) of computational Ω-algebras (where D⊆{0,1}^*) is called polynomially bounded (resp., having exponential size) if there exists a polynomial η such that for all d∈D, the length of any representation of every h∈H_d is at most η(∣d∣) (resp., |H_d|≤2^{η(|d|)}). First, we prove the following trichotomy: (i) if consists of nullary operation symbols only, then there exists a polynomially bounded pseudo-free family; (ii) if Ω=Ω_0∪{ω}, where Ω_0 consists of nullary operation symbols and the arity of ω is 1, then there exist an exponential-size pseudo-free family and a polynomially bounded weakly pseudo-free family; (iii) in all other cases, the existence of polynomially bounded weakly pseudo-free families implies the existence of collision-resistant families of hash functions. In this trichotomy, (weak) pseudo-freeness is meant in the variety of all Ω-algebras. Second, assuming the existence of collision-resistant families of hash functions, we construct a polynomially bounded weakly pseudo-free family and an exponential-size pseudo-free family in the variety of all m-ary groupoids, where m is an arbitrary positive integer.