<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
  src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (Thelma) - Chapter 5: Multi-Valued Threshold Elements</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap5"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap4_mj.html">[Previous Chapter]</a>    <a href="chapBib_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap5.html">[MathJax off]</a></p>
<p><a id="X8735CBCC80897D83" name="X8735CBCC80897D83"></a></p>
<div class="ChapSects"><a href="chap5_mj.html#X8735CBCC80897D83">5 <span class="Heading">Multi-Valued Threshold Elements</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.html#X83640D4B7FFE0F9F">5.1 <span class="Heading">Threshold Elements over <span class="SimpleMath">\(GF(p^k)\)</span></span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X818FF66D7919D8B1">5.1-1 MVThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7C4A761F864B8EFA">5.1-2 IsMVThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7E64FB7684207AED">5.1-3 OutputOfMVThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7B2520F37C18CC81">5.1-4 StructureOfMVThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5_mj.html#X7B103C6B7EB903EF">5.1-5 MVBooleanFunctionBySTE</a></span>
</div></div>
</div>

<h3>5 <span class="Heading">Multi-Valued Threshold Elements</span></h3>

<p><a id="X83640D4B7FFE0F9F" name="X83640D4B7FFE0F9F"></a></p>

<h4>5.1 <span class="Heading">Threshold Elements over <span class="SimpleMath">\(GF(p^k)\)</span></span></h4>

<p>Let <span class="SimpleMath">\(F=GF(p^k)\)</span> be a Galois field with primitive element <span class="SimpleMath">\(\varepsilon\)</span> and let <span class="SimpleMath">\(F^*\)</span> be the multiplicative group of <span class="SimpleMath">\(F\)</span>. Let us consider all proper subgroups of <span class="SimpleMath">\(F^*\)</span>:</p>

<p class="center">\[
  C_{j_1}= \langle \sigma_1 \mid \sigma_1^{j_1}=1 \rangle, \ldots , C_{j_t}= \langle \sigma_t \mid \sigma_n^{j_t}=1 \rangle,
\]</p>

<p>where <span class="SimpleMath">\(\sigma_i=\epsilon^{\frac{|F^*|}{j_i}}\)</span> (<span class="SimpleMath">\(i=1,\ldots,t\)</span>)are the generators of the corresponding cyclic groups. Denote <span class="SimpleMath">\(T=\{ j_1, \ldots, j_t\} \)</span>. Let <span class="SimpleMath">\(G_n = C_{k_1}\otimes \ldots \otimes C_{k_n}\)</span> be a direct product of cyclic groups <span class="SimpleMath">\(C_{k_i}\)</span> (<span class="SimpleMath">\(k_i \in T\)</span>,<span class="SimpleMath">\(i=1,\ldots,n\)</span>).</p>

<p>A <var class="Arg">discrete function</var> of <span class="SimpleMath">\(n\)</span> variables over a finite field <span class="SimpleMath">\(F\)</span> is a mapping <span class="SimpleMath">\(f:G_n \to C_q \)</span>, <span class="SimpleMath">\(q \in T \)</span>, <span class="SimpleMath">\(C_q = \langle \sigma \mid \sigma^{q}=1 \rangle \)</span>, <span class="SimpleMath">\(\sigma = \epsilon^{\frac{|F^*|}{q}}\)</span>.</p>

<p>We define the function <span class="SimpleMath">\(FSign\xi\)</span> in the following way <a href="chapBib_mj.html#biBGeche2010">[Gec10]</a>:</p>

<p class="center">\[
\forall \xi \in F^* : FSign \xi = \sigma^j, \;\; \textrm{if} \;\; \frac{j|F^*|}{q}\leq \textrm{deg}\xi < \frac{(j+1)|F^*|}{q},
\]</p>

<p>in which <span class="SimpleMath">\(\textrm{deg} \xi\)</span> is obtained from the equality <span class="SimpleMath">\(\xi=\epsilon^{\textrm{deg} \xi}\)</span>, <span class="SimpleMath">\(j \in \{ 1, \ldots , q-1 \}\)</span>.</p>

<p>Let <span class="SimpleMath">\((w_1, \ldots, w_n; T) \in F^{n+1} \)</span>. For all <span class="SimpleMath">\(\overline{g} = (x_1,\ldots,x_n) \in G_n \)</span> (i.e. <span class="SimpleMath">\(x_j \in C_{k_j}\)</span>) we define</p>

<p class="center">\[
w(\overline{g}) = \sum_{i=1}^n w_i x_i + T \in F.
\]</p>

<p>A <var class="Arg">neural element</var> with structure vector <span class="SimpleMath">\((w_1, \ldots, w_n; T) \in F^{n+1} \)</span> is a logic device that realizes the function <span class="SimpleMath">\(FSign (w(\overline{g})) \)</span> for all <span class="SimpleMath">\( \overline{g} \in G_n \)</span>.</p>

<p>Discrete function <span class="SimpleMath">\(f\)</span> which is relizable by a single neural element over the field <span class="SimpleMath">\(F\)</span> is called <var class="Arg">neurofunction</var>.</p>

<p><a id="X818FF66D7919D8B1" name="X818FF66D7919D8B1"></a></p>

<h5>5.1-1 MVThresholdElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; MVThresholdElement</code>( <var class="Arg">Structure</var>, <var class="Arg">Dimensions</var>, <var class="Arg">Field</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the two-element list <code class="code">Structure</code>, in which the first element is a vector over the field <code class="code">Field</code>, and the second element is an element of the <code class="code">Field</code>, a list of positive integers <code class="code">Dimensions</code> (or an integerm if all the dimensions are equal) and a Galois field <code class="code">Field</code> the function <code class="code">MVThresholdElement</code> returns a multi-valued threshold element with the number of inputs equal to the length of the first element of <code class="code">Structure</code> list.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">F:=GF(13);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">st:=[[Z(13)^5,Z(13)^7],Z(13)^4];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">dim:=[2,3,3];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mvte:=MVThresholdElement(st,dim,F);</span>
< multivalued threshold element over GF(13) with structure [[ 6, 11 ], 3] and
  dimension vector [ 2, 3, 3 ] >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(mvte);</span>
Structure vector = [[ 6, 11 ], 3]
Dimension vector = [[ 2, 3, 3 ]]
Field: GF(13)
Multi-Valued Threshold Element realizes the function f :
[ 1, 1 ]  ||  9
[ 1, 3 ]  ||  3
[ 1, 9 ]  ||  1
[ 12, 1 ]  ||  1
[ 12, 3 ]  ||  1
[ 12, 9 ]  ||  9
<span class="GAPprompt">gap></span> <span class="GAPinput">## If all dimensions in dimension vector are equal, the user can enter</span>
just this number.
<span class="GAPprompt">gap></span> <span class="GAPinput">F:=GF(5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">st:=[[Z(5)^0,Z(5)^0],Z(5)^2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">dim:=2;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mvte:=MVThresholdElement(st,dim,F);</span>
< multivalued threshold element over GF(5) with structure [[ 1, 1 ], 4] and
  dimension vector [ 2, 2, 2 ] >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(mvte);</span>
Structure vector = [[ 1, 1 ], 4]
Dimension vector = [[ 2, 2, 2 ]]
Field: GF(5)
Multi-Valued Threshold Element realizes the function f :
[ 1, 1 ]  ||  1
[ 1, 4 ]  ||  4
[ 4, 1 ]  ||  4
[ 4, 4 ]  ||  1

</pre></div>

<p>The function <code class="code">Display</code> outputs the stucture of the given threshold element <code class="code">mvte</code> and the truth table in given alphabet. In the previous example <code class="code">mvte</code> realizes a three-valued function in <span class="SimpleMath">\(\{ 1, 3, 9 \}\)</span> alphabet over GF(13).</p>

<p><a id="X7C4A761F864B8EFA" name="X7C4A761F864B8EFA"></a></p>

<h5>5.1-2 IsMVThresholdElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsMVThresholdElement</code>( <var class="Arg">Obj</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the object <code class="code">Obj</code> the function <code class="code">IsMVThresholdElement</code> returns <code class="code">true</code> if <code class="code">Obj</code> is a multi-valued threshold element (see <code class="func">MVThresholdElement</code> (<a href="chap5_mj.html#X818FF66D7919D8B1"><span class="RefLink">5.1-1</span></a>)), and <code class="code">false</code> otherwise.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">IsMVThresholdElement(mvte);</span>
true

</pre></div>

<p><a id="X7E64FB7684207AED" name="X7E64FB7684207AED"></a></p>

<h5>5.1-3 OutputOfMVThresholdElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; OutputOfMVThresholdElement</code>( <var class="Arg">MVThrEl</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the multi-valued threshold element <code class="code">MVThrEl</code> the function <code class="code">OutputOfMVThresholdElement</code> returns the truth vector of the multi-valued Boolean function, realized by <code class="code">MVThrEl</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">F:=GF(13);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">st:=[[Z(13)^5,Z(13)^7],Z(13)^4];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">dim:=[2,3,3];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mvte:=MVThresholdElement(st,dim,F);</span>
< multivalued threshold element over GF(13) with structure [[ 6, 11 ], 3] and
  dimension vector [ 2, 3, 3 ] >
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=OutputOfMVThresholdElement(mvte);</span>
< logic function of 2 variables and dimension vector [ 2, 3, 3 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(f);</span>
[ 0, 0 ] || 2
[ 0, 1 ] || 1
[ 0, 2 ] || 0
[ 1, 0 ] || 0
[ 1, 1 ] || 0
[ 1, 2 ] || 2

</pre></div>

<p><a id="X7B2520F37C18CC81" name="X7B2520F37C18CC81"></a></p>

<h5>5.1-4 StructureOfMVThresholdElement</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; StructureOfMVThresholdElement</code>( <var class="Arg">MVThrEl</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the multi-valued threshold element <code class="code">MVThrEl</code> the function <code class="code">StructureOfMVThresholdElement</code> returns the structure vector of <code class="code">MVThrEl</code> (see <code class="func">MVThresholdElement</code> (<a href="chap5_mj.html#X818FF66D7919D8B1"><span class="RefLink">5.1-1</span></a>)).</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">StructureOfMVThresholdElement(mvte);</span>
[ [ Z(13)^5, Z(13)^7 ], Z(13)^4 ]

</pre></div>

<p><a id="X7B103C6B7EB903EF" name="X7B103C6B7EB903EF"></a></p>

<h5>5.1-5 MVBooleanFunctionBySTE</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; MVBooleanFunctionBySTE</code>( <var class="Arg">Func</var>, <var class="Arg">Dim</var>, <var class="Arg">F</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>For the given multi-valued function <code class="code">Func</code> and the prime field <code class="code">F</code> the function <code class="code">MVBooleanFunctionBySTE</code> returns the multi-valued threshold element over <code class="code">F</code> if <code class="code">Func</code> is realizable and an empty list otherwise. The algorithm realizing this function was proposed in <a href="chapBib_mj.html#biBGeche2010">[Gec10]</a>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,2,[0,1,1,0]);</span>
< Boolean function of 2 variables >
<span class="GAPprompt">gap></span> <span class="GAPinput">mvte:=MVBooleanFunctionBySTE(f,GF(3));</span>
[  ]
<span class="GAPprompt">gap></span> <span class="GAPinput">mvte:=MVBooleanFunctionBySTE(f,GF(5));</span>
< multivalued threshold element over GF(5) with structure [[ 1, 1 ], 4] and
  dimension vector [ 2, 2, 2 ] >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
Structure vector = [[ 1, 1 ], 4]
Dimension vector = [[ 2, 2, 2 ]]
Field: GF(5)
Multi-Valued Threshold Element realizes the function f :
[ 1, 1 ]  ||  1
[ 1, 4 ]  ||  4
[ 4, 1 ]  ||  4
[ 4, 4 ]  ||  1
<span class="GAPprompt">gap></span> <span class="GAPinput">## Consider an example if dimensions are presented as a list.</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=LogicFunction(2,[2,3,3],[0,0,1,1,2,2]);</span>
< logic function of 2 variables and dimension vector [ 2, 3, 3 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">mvte:=MVBooleanFunctionBySTE(f,GF(13));</span>
< multivalued threshold element over GF(13) with structure [[ 12, 10 ], 5]
  and dimension vector [ 2, 3, 3 ] >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
Structure vector = [[ 12, 10 ], 5]
Dimension vector = [[ 2, 3, 3 ]]
Field: GF(13)
Multi-Valued Threshold Element realizes the function f :
[ 1, 1 ]  ||  1
[ 1, 3 ]  ||  1
[ 1, 9 ]  ||  3
[ 12, 1 ]  ||  3
[ 12, 3 ]  ||  9
[ 12, 9 ]  ||  9


</pre></div>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap4_mj.html">[Previous Chapter]</a>    <a href="chapBib_mj.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>