In
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
and
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
, a ranked alphabet is a pair of an
ordinary alphabet ''F'' and a function ''Arity'': ''F''→
. Each letter in ''F'' has its
arity
Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. In ...
so it can be used to build
terms. Nullary elements (of zero arity) are also called constants. Terms built with unary symbols and constants can be considered as
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
. Higher arities lead to proper
trees
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
.
For instance, in the term
:
,
''a,b,c'' are constants, ''g'' is unary, and ''f'' is ternary.
Contrariwise,
:
cannot be a valid term, as the symbol ''f'' appears once as binary, and once as unary, which is illicit, as ''Arity'' must be a function.
References
*
{{Comp-sci-theory-stub
Trees (data structures)
Automata (computation)
Formal languages
Theoretical computer science