Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/thelma/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 3.2.2022 mit Größe 14 kB image not shown  

Quelle  chap5.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/thelma/doc/chap5.html


<?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>
<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.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap4.html">[Previous Chapter]</a>    <a href="chapBib.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap5_mj.html">[MathJax on]</a></p>
<p><a id="X8735CBCC80897D83" name="X8735CBCC80897D83"></a></p>
<div class="ChapSects"><a href="chap5.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.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.html#X818FF66D7919D8B1">5.1-1 MVThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.html#X7C4A761F864B8EFA">5.1-2 IsMVThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.html#X7E64FB7684207AED">5.1-3 OutputOfMVThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.html#X7B2520F37C18CC81">5.1-4 StructureOfMVThresholdElement</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.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">ε</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="pcenter">
  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">σ_i=ϵ^frac|F^*|j_i}</span> (<span class="SimpleMath">i=1,...,t</span>)are the generators of the corresponding cyclic groups. Denote <span class="SimpleMath">T={ j_1, ..., j_t}</span>. Let <span class="SimpleMath">G_n = C_k_1⊗ ... ⊗ C_k_n</span> be a direct product of cyclic groups <span class="SimpleMath">C_k_i</span> (<span class="SimpleMath">k_i ∈ T</span>,<span class="SimpleMath">i=1,...,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 -> C_q</span>, <span class="SimpleMath">q ∈ T</span>, <span class="SimpleMath">C_q = ⟨ σ ∣ σ^q=1 ⟩</span>, <span class="SimpleMath">σ = ϵ^frac|F^*|q}</span>.</p>

<p>We define the function <span class="SimpleMath">FSignξ</span> in the following way <a href="chapBib.html#biBGeche2010">[Gec10]</a>:</p>

<p class="pcenter">
\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">deg ξ</span> is obtained from the equality <span class="SimpleMath">ξ=ϵ^deg ξ</span>, <span class="SimpleMath">j ∈ { 1, ... , q-1 }</span>.</p>

<p>Let <span class="SimpleMath">(w_1, ..., w_n; T) ∈ F^n+1</span>. For all <span class="SimpleMath">overlineg = (x_1,...,x_n) ∈ G_n</span> (i.e. <span class="SimpleMath">x_j ∈ C_k_j</span>) we define</p>

<p class="pcenter">
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, ..., w_n; T) ∈ F^n+1</span> is a logic device that realizes the function <span class="SimpleMath">FSign (w(overlineg))</span> for all <span class="SimpleMath">overlineg ∈ 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">‣ 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">‣ 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.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">‣ 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">‣ 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.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">‣ 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.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.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap4.html">[Previous Chapter]</a>    <a href="chapBib.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.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>

100%


¤ Dauer der Verarbeitung: 0.17 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.