请输入您要查询的字词:

 

单词 StraightlineProgram
释义

straight-line program


Definition 1.

Given a set S, a straight-line program (SLP) is a family of functions F={fi:1im}

fi:Sn+iS

for some fixed nN. An SLP is evaluated on a tuple(s1,,sn) by recursion in the following way: f1 is evaluatedon (s1,,sn) as a function. The remaining evaluations arerecursive. So f2(s1,,sn) denotes

f2(s1,,sn):=f2(s1,,sn,f1(s1,,sn)).

and in general

fi+1(s1,,sn):=fi+1(s1,,sn,f1(s1,,sn),,fi(s1,,sn)).

The final output fm(s1,,sn) is denoted F(s1,,sn).In this way we treat F as function from SnS.

SLPs arrise from the multiple meansings of expressions of the sort anin a some algebraic structurePlanetmathPlanetmath S. First of all, one can formally treat an as the word aa in S. Secondly this can be interpreted as the actual result of this mulitplication.

In the former meaning, actually storing a word of the form an asaa is difficult hence it is abreviated. Other examples includewords such as a10(bc)6 where the values of a,b,c are continually changing or even unknown. Here an SLP can encode this word in such a waythat if we replace a by bc, then the resulting new word would resultsimply by evaluation the SLP at the input (bc,b,c) instead of (a,b,c).

In the second treatment where we whish to actually evaluate an and the like,we find the problem of understanding what an means as a program.Certainly we may have a4=(aa)(aa)=a(a(aa)) etc. However this equivalenceneglects the problem of selecting a method of computing the result. Usuallyan efficient method is desired. An SLP developed from simple functionsMathworldPlanetmathsuch as f(x)=x2 and f(x,y)=x+y formally address this problem.

The term straight-line reflects the fact that evaluating an SLP canbe achieved by a program which does not branch or loop so its execution isa straight-line. It is common for SLPs to be built entirely from simplefunctions such as f(x,y)=x+y or f(x)=x×x.

Because each element fi of an SLP is evaluated externally only on s1,,sn and the remaining inputs come internally from previous fj,1ji, it is convient to write definitions for fi as takinginputs only from (s1,,sn) and implicitly allowing for the use ofthe outputs of previous fj’s.

SLPs can be defined in contexts other than semigroupsPlanetmathPlanetmath including rings, modules, and polynomialsMathworldPlanetmathPlanetmath. Although they arise naturally to compress computations, they are also useful in describing smaller bounds for many combinatorial theorems related to algebraic objects.

It is possible for a function f:SnS to be defined equivalently by multiple SLPs and so a notion of equality of SLPs is stronger than equivalence of final outputs.

Definition 2.

Two SLPs F={fi:1im} and G={gi:1ik} are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath if F and G can be evaluatedon the same inputs and for every input (s1,,sn), F(s1,,sn)=G(s1,,sn).When and SLP F is equivalent to a trivial SLP {f:SnS} we say that F is an SLP representation of f.

Every function f:SnS can be expressed as an SLP trivially by={f}. However, this SLP is typically the least optimal for the actual evaluation of the output for a given input. This leads to a hierarchy imposed on equivalent SLPs based on their associated computational length.

Definition 3.

If an SLP represents an algebraic expression (alternatively a word in the generatorsPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath) in the semigroup S then thecomputational length or simply length of the SLP is the maximum number of multiplications in the semigroup performed to evaluate the expressionusing the SLP.

It is evident that the trivial SLP of an algebraic expression has length equal to the length of the word.

Titlestraight-line program
Canonical nameStraightlineProgram
Date of creation2013-03-22 16:16:02
Last modified on2013-03-22 16:16:02
OwnerAlgeboy (12884)
Last modified byAlgeboy (12884)
Numerical id10
AuthorAlgeboy (12884)
Entry typeDefinition
Classificationmsc 08A99
Classificationmsc 20A05
Classificationmsc 20-00
Related topicword
Related topicWord
Definesstraight-line program
DefinesSLP
DefinesSLP representation
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 10:36:04