complexity function

== English == === Noun === complexity function (plural complexity functions) (group theory, computing theory, of a string) A function that counts the number of distinct factors (substrings of consecutive symbols) in a string of symbols;(of a formal language) a function that counts the number of words of a given length. 2003, Julien Cassaigne, Constructing Infinite Words of Intermediate Complexity, Masami Ito, Masafumi Toyama (editors), Developments in Language Theory: 6th International Conference, 6th International Conference, DLT 2002, Revised Papers, Springer, LNCS 2450, page 173, We present two constructions of infinite words with a complexity function that grows faster than any polynomial, but slower than any exponential. (computing theory, of an algorithm) A function representing the computational complexity an algorithm. 2003, Roberto Segala, Verification of Randomized Distributed Algorithms, Ed Brinksma, Holger Hermanns, Joost-Pieter Katoen (editors), Lectures on Formal Methods and Performance Analysis, Springer, LNCS 2090, page 253, Let ϕ {\displaystyle \phi } be a complexity function. ==== Derived terms ==== abelian complexity function group complexity function time complexity function volume complexity function ==== Translations ==== === Further reading === Computational complexity on Wikipedia.Wikipedia Formal language on Wikipedia.Wikipedia Sparse language on Wikipedia.Wikipedia