This HTML5 document contains 44 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n15https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:MPSolve
dbo:wikiPageWikiLink
dbr:Straight-line_program
Subject Item
dbr:Magma_(computer_algebra_system)
dbo:wikiPageWikiLink
dbr:Straight-line_program
Subject Item
dbr:Straight-line_program
rdf:type
dbo:Ship
rdfs:label
Straight-line program
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.
dct:subject
dbc:Algebra
dbo:wikiPageID
45235652
dbo:wikiPageRevisionID
1063626858
dbo:wikiPageWikiLink
dbr:Dihedral_group dbr:ATLAS_of_Finite_Groups dbr:Suzuki_groups dbr:Mathematics dbr:First-order_logic dbr:Computational_group_theory dbc:Algebra dbr:Computer_algebra_system dbr:Cayley_graph dbr:Black_box_group
owl:sameAs
wikidata:Q25344628 n15:2PL29
dbp:wikiPageUsesTemplate
dbt:Math_proof dbt:Mabs dbt:Col-end dbt:Col-begin dbt:Col-break dbt:Math_theorem dbt:Not_a_typo dbt:Math dbt:Su dbt:! dbt:Reflist
dbp:b
j 1
dbp:p
−1
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|) in every generating set. An efficient solution to the constructive membership problem is crucial to many group-theoretic algorithms. It can be stated in terms of SLPs as follows. Given a finite group G = ⟨S⟩ and g ∈ G, find a straight-line program computing g over S. The constructive membership problem is often studied in the setting of black box groups. The elements are encoded by bit strings of a fixed length. Three oracles are provided for the group-theoretic functions of multiplication, inversion, and checking for equality with the identity. A black box algorithm is one which uses only these oracles. Hence, straight-line programs for black box groups are black box algorithms. Explicit straight-line programs are given for a wealth of finite simple groups in the online ATLAS of Finite Groups.
gold:hypernym
dbr:L
prov:wasDerivedFrom
wikipedia-en:Straight-line_program?oldid=1063626858&ns=0
dbo:wikiPageLength
13567
foaf:isPrimaryTopicOf
wikipedia-en:Straight-line_program
Subject Item
dbr:Straight-line_grammar
dbo:wikiPageWikiLink
dbr:Straight-line_program
Subject Item
dbr:Re-Pair
dbo:wikiPageWikiLink
dbr:Straight-line_program
Subject Item
dbr:SLP
dbo:wikiPageWikiLink
dbr:Straight-line_program
dbo:wikiPageDisambiguates
dbr:Straight-line_program
Subject Item
wikipedia-en:Straight-line_program
foaf:primaryTopic
dbr:Straight-line_program