Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Straight-line_program> ?p ?o }
Showing triples 1 to 26 of
26
with 100 triples per page.
- Straight-line_program 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 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.".
- Straight-line_program wikiPageID "45235652".
- Straight-line_program wikiPageLength "13126".
- Straight-line_program wikiPageOutDegree "9".
- Straight-line_program wikiPageRevisionID "708147385".
- Straight-line_program wikiPageWikiLink ATLAS_of_Finite_Groups.
- Straight-line_program wikiPageWikiLink Black_box_group.
- Straight-line_program wikiPageWikiLink Cayley_graph.
- Straight-line_program wikiPageWikiLink Computational_algebra.
- Straight-line_program wikiPageWikiLink Computational_group_theory.
- Straight-line_program wikiPageWikiLink Dihedral_group.
- Straight-line_program wikiPageWikiLink First-order_logic.
- Straight-line_program wikiPageWikiLink Mathematics.
- Straight-line_program wikiPageWikiLink Suzuki_groups.
- Straight-line_program wikiPageWikiLinkText "straight-line program".
- Straight-line_program wikiPageUsesTemplate Template:Col-begin.
- Straight-line_program wikiPageUsesTemplate Template:Col-break.
- Straight-line_program wikiPageUsesTemplate Template:Col-end.
- Straight-line_program wikiPageUsesTemplate Template:Reflist.
- Straight-line_program wikiPageUsesTemplate Template:Uncategorized.
- Straight-line_program hypernym L.
- Straight-line_program type Ship.
- Straight-line_program 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 belongs to S, is the inverse of a preceding element, or the product of two preceding elements.".
- Straight-line_program label "Straight-line program".
- Straight-line_program wasDerivedFrom Straight-line_program?oldid=708147385.
- Straight-line_program isPrimaryTopicOf Straight-line_program.