In computer science and mathematics, more precisely in automata theory, model theory and formal language, a regular numerical predicate is a kind of relation over integers. Regular numerical predicates can also be considered as a subset of N r {\displaystyle \mathbb {N} ^{r}} for some arity r {\displaystyle r} . One of the main interests of this class of predicates is that it can be defined in plenty of different ways, using different logical formalisms. Furthermore, most of the definitions use only basic notions, and thus allows to relate foundations of various fields of fundamental computer science such as automata theory, syntactic semigroup, model theory and semigroup theory. The class of regular numerical predicate is denoted C l c a {\displaystyle {\mathcal {C}}_{lca}} , N t h r e s , m o d {\displaystyle {\mathcal {N}}_{\mathtt {thres,mod}}} and REG.
Definitions The class of regular numerical predicate admits a lot of equivalent definitions. They are now given. In all of those definitions, we fix r ∈ N {\displaystyle r\in \mathbb {N} } and P ⊆ N r {\displaystyle P\subseteq \mathbb {N} ^{r}} a (numerical) predicate of arity r {\displaystyle r} .
Automata with variables The first definition encodes predicate as a formal language. A predicate is said to be regular if the formal language is regular. Let the alphabet A {\displaystyle A} be the set of subset of { 1 , … , r } {\displaystyle \{1,\dots ,r\}} . Given a vector of r {\displaystyle r} integers n = ( n 0 , … , n r − 1 ) ∈ N r {\displaystyle \mathbf {n} =(n_{0},\dots ,n_{r-1})\in \mathbb {N} ^{r}} , it is represented by the word n ¯ {\displaystyle {\overline {\mathbf {n} }}} of length max ( n 0 , … , n r − 1 ) {\displaystyle \max(n_{0},\dots ,n_{r-1})} whose i {\displaystyle i} -th letter is { j ∣ n j = i } {\displaystyle \{j\mid n_{j}=i\}} . For example, the vector ( 3 , 1 , 3 ) {\displaystyle (3,1,3)} is represented by the word ∅ { 1 } ∅ { 0 , 2 } {\displaystyle \emptyset \{1\}\emptyset \{0,2\}} . We then define P ¯ {\displaystyle {\overline {P}}} as { n ¯ ∣ n } {\displaystyle \{{\overline {\mathbf {n} }}\mid \mathbf {n} \}} . The numerical predicate P {\displaystyle P} is said to be regular if P ¯ {\displaystyle {\overline {P}}} is a regular language over the alphabet A {\displaystyle A} . This is the reason for the use of the word "regular" to describe this kind of numerical predicate.
… excerpt ends here. Continue reading the full article.
