Straight-line program (original) (raw)
In mathematics, more specifically in computational algebra, a straight-line program (SLP) for a finite group G = ⟨S⟩ is a finite sequence L of elements of G such that every element of L either belongs to S, is the inverse of a preceding element, or the product of two preceding elements. An SLP L is said to compute a group element g ∈ G if g ∈ L, where g is encoded by a word in S and its inverses. Explicit straight-line programs are given for a wealth of finite simple groups in the online ATLAS of Finite Groups.
| Property | Value |
|---|---|
| dbo:abstract | In mathematics, more specifically in computational algebra, a straight-line program (SLP) for a finite group G = ⟨S⟩ is a finite sequence L of elements of G such that every element of L either belongs to S, is the inverse of a preceding element, or the product of two preceding elements. An SLP L is said to compute a group element g ∈ G if g ∈ L, where g is encoded by a word in S and its inverses. Intuitively, an SLP computing some g ∈ G is an efficient way of storing g as a group word over S; observe that if g is constructed in i steps, the word length of g may be exponential in i, but the length of the corresponding SLP is linear in i. This has important applications in computational group theory, by using SLPs to efficiently encode group elements as words over a given generating set. Straight-line programs were introduced by Babai and Szemerédi in 1984 as a tool for studying the computational complexity of certain matrix group properties. Babai and Szemerédi prove that every element of a finite group G has an SLP of length O(log2|G |
| dbo:wikiPageID | 45235652 (xsd:integer) |
| dbo:wikiPageLength | 13567 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1063626858 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Mathematics dbr:Computational_group_theory dbr:Computer_algebra_system dbc:Algebra dbr:First-order_logic dbr:Cayley_graph dbr:ATLAS_of_Finite_Groups dbr:Black_box_group dbr:Dihedral_group dbr:Suzuki_groups |
| dbp:b | 1 (xsd:integer) j (en) |
| dbp:p | −1 (en) |
| dbp:wikiPageUsesTemplate | dbt:! dbt:Col-begin dbt:Col-break dbt:Col-end dbt:Math dbt:Not_a_typo dbt:Reflist dbt:Math_proof dbt:Su dbt:Mabs dbt:Math_theorem |
| dcterms:subject | dbc:Algebra |
| gold:hypernym | dbr:L |
| rdf:type | dbo:Ship |
| rdfs:comment | In mathematics, more specifically in computational algebra, a straight-line program (SLP) for a finite group G = ⟨S⟩ is a finite sequence L of elements of G such that every element of L either belongs to S, is the inverse of a preceding element, or the product of two preceding elements. An SLP L is said to compute a group element g ∈ G if g ∈ L, where g is encoded by a word in S and its inverses. Explicit straight-line programs are given for a wealth of finite simple groups in the online ATLAS of Finite Groups. (en) |
| rdfs:label | Straight-line program (en) |
| owl:sameAs | wikidata:Straight-line program https://global.dbpedia.org/id/2PL29 |
| prov:wasDerivedFrom | wikipedia-en:Straight-line_program?oldid=1063626858&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Straight-line_program |
| is dbo:wikiPageDisambiguates of | dbr:SLP |
| is dbo:wikiPageWikiLink of | dbr:MPSolve dbr:Magma_(computer_algebra_system) dbr:Straight-line_grammar dbr:Re-Pair dbr:SLP |
| is foaf:primaryTopic of | wikipedia-en:Straight-line_program |