{
  "id": "enwiki-001368958053",
  "slug": "regular-numerical-predicate",
  "title": "Regular numerical predicate",
  "qid": "",
  "lead": "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 \\mathbb N^r for some arity 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 \\mathcal C_{lca} , \\mathcal N_{\\mathtt{thres, mod}} and REG.",
  "body": "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 \\mathbb N^r for some arity 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 \\mathcal C_{lca} , \\mathcal N_{\\mathtt{thres, mod}} and REG. Let the alphabet A be the set of subset of \\{1,\\dots,r\\} . Given a vector of r integers \\mathbf n=(n_0,\\dots,n_{r-1})\\in\\mathbb N^r , it is represented by the word \\overline{\\mathbf n} of length \\max(n_0,\\dots,n_{r-1}) whose i -th letter is \\{j\\mid n_j=i\\} . For example, the vector (3,1,3) is represented by the word \\emptyset\\{1\\}\\emptyset\\{0,2\\} . We then define \\overline P as \\{\\overline {\\mathbf n}\\mid\\mathbf n\\} . The numerical predicate P is said to be regular if \\overline P is a regular language over the alphabet A . This is the reason for the use of the word \"regular\" to describe this kind of numerical predicate. Given a vector of r integers \\mathbf n=(n_0,\\dots,n_{r-1})\\in\\mathbb N^r , let l=\\max(n_0,\\dots,n_{r-1}) . The vector \\mathbf n is represented by the word \\overline{\\mathbf n}\\in\\left(\\{0,1\\}^r\\right)^* such that, the projection of \\overline{\\mathbf n} over its i -th component is \\mid{n_i}\\mid_{\\max(n_0,\\dots,n_{r-1})} . For example, the representation of (3,1,3) is \\begin{array}{l|l|l}1&1&1\\\\1&0&0\\\\1&1&1\\end{array} . This is a word whose letters are the vectors (1,1,1) , (1,0,1) and (1,0,1) and whose projection over each components are 111 , 100 and 111 . As in the previous definition, the numerical predicate P is said to be regular if \\overline P is a regular language over the alphabet A . A predicate is regular if and only if it can be defined by a monadic second order formula \\phi(x_0,\\dots,x_{r-1}) , or equivalently by an existential monadic second order formula, where the only atomic predicate is the successor function y+1=z . the addition of a constant x_i+c=x_j , with c an integral constant, the order relation x_i\\le x_j , the modular relations, with a fixed modular value. That is, predicates of the form x_i\\equiv c\\mod m where c and m are fixed constants and x is a variable. A predicate is regular if and only if it can be defined in the language of congruence arithmetic. The equivalence with previous definition is due to quantifier elimination. In order to introduce the definition of m -regular, the trivial case where r=0 should be considered separately. When r=0 , then the predicate P is either the constant true or the constant false. Those two predicates are said to be m -regular (for every m ). Let us now assume that r\\ge1 . In order to introduce the definition of regular predicate in this case, we need to introduce the notion of section of a predicate. The section P^{x_i=c} of P is the predicate of arity r-1 where the i -th component is fixed to c . Formally, it is defined as \\{(x_0,\\dots,x_{i-1},x_{i+1},\\dots,x_{r-1})\\mid P(x_0,\\dots,x_{i-1},c,x_{i+1},\\dots,x_{r-1})\\} . For example, let us consider the sum predicate S=\\{(n_0,n_1,n_2)\\mid n_0+n_1=n_2\\} . Then S^{x_0=c}=\\{(n_1,n_2)\\mid c+n_1=n_2\\} is the predicate which adds the constant c , and S^{x_2=c}=\\{(n_0,n_1)\\mid n_0+n_1=c\\} is the predicate which states that the sum of its two elements is c . The last equivalent definition of regular predicate can now be given. A predicate P of arity r\\ge1 is m -regular if it satisfies the two following conditions: all of its sections are m -regular, there exists a threshold t\\in\\mathbb N such that, for each vectors (n_0,\\dots,n_r)\\in\\mathbb N^r with each n_i\\ge t , P(n_0,\\dots,n_r)\\iff P(n_0+m,\\dots,n_r+m) . The second property intuitively means that, when number are big enough, then their exact value does not matter. The properties which matters are the order relation between the numbers and their value modulo the period m . Given a subset s\\subseteq\\{0,\\dots,r-1\\} , let \\overline s be the characteristic vector of s . That is, the vector in \\{0,1\\}^r whose i -th component is 1 if i\\in s , and 0 otherwise. Given a sequence \\mathbf s=s_0\\subsetneq\\dots\\subsetneq s_{p-1} of sets, let P_{\\mathbf s}=\\{(n_0,\\dots,n_{p-1})\\in\\mathbb N^p\\mid P(\\sum n_ie_i)\\} . The predicate P is regular if and only if for each increasing sequence of set \\mathbf s , P_{\\mathbf s} is a recognizable submonoid of \\mathbb N^p . ==References==",
  "categories": [
    "22914973",
    "23933915",
    "23933957",
    "24723435",
    "24745122",
    "25574325",
    "26696192",
    "27894481"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1368958053",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1786493853.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001368958053",
    "type": "webpage",
    "title": "Regular numerical predicate",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/regular-numerical-predicate",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001368958053",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1368958053",
    "note": "Immutable snapshot enwiki-001368958053"
  }
}