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

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

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n9https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
n20http://dbpedia.org/resource/Talk:
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n10http://www.emis.de/journals/SLC/books/
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/
n17http://citeseer.ist.psu.edu/

Statements

Subject Item
dbr:Trace_monoid
rdf:type
yago:Whole100003553 yago:Artifact100021939 yago:Structure104341686 yago:PhysicalEntity100001930 yago:WikicatFreeAlgebraicStructures yago:YagoPermanentlyLocatedEntity yago:YagoGeoEntity yago:Object100002684
rdfs:label
Monoïde des traces Trace monoid
rdfs:comment
In computer science, a trace is a set of strings, wherein certain letters in the string are allowed to commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order, but allowing certain reshufflings to take place. Traces were introduced by Pierre Cartier and Dominique Foata in 1969 to give a combinatorial proof of MacMahon's master theorem. Traces are used in theories of concurrent computation, where commuting letters stand for portions of a job that can execute independently of one another, while non-commuting letters stand for locks, synchronization points or thread joins. En mathématiques et en informatique, une trace est un ensemble de mots, où certaines lettres peuvent commuter, et d'autres non. Le monoïde des traces oumonoïde partiellement commutatif libre est le monoïde quotient dumonoïde libre par une relation de commutation de lettres.
dcterms:subject
dbc:Formal_languages dbc:Combinatorics dbc:Free_algebraic_structures dbc:Semigroup_theory dbc:Trace_theory
dbo:wikiPageID
10739141
dbo:wikiPageRevisionID
1118361208
dbo:wikiPageWikiLink
dbr:Lecture_Notes_in_Computer_Science dbr:History_monoid dbr:Free_monoid dbr:Dominique_Foata dbc:Formal_languages dbr:Donald_Knuth dbr:String_operations dbr:Dependency_relation dbr:Trace_theory dbr:Monoid dbc:Trace_theory dbr:Universal_property dbr:Concatenation dbr:MacMahon's_master_theorem dbr:Dependency_graph dbr:Levi's_lemma dbr:Parallel_computing dbc:Combinatorics dbr:Graph_(discrete_mathematics) dbr:Process_calculus dbr:Kleene_star dbr:Combinatoric dbr:Synchronization_(computer_science) dbr:Computer_science dbr:Isomorphism dbr:Transitive_closure n20:Trace_monoid dbr:Pierre_Cartier_(mathematician) dbr:Thread_(computing) dbr:Natural_transformation dbr:Formal_language dbc:Free_algebraic_structures dbr:Trace_cache dbr:Congruence_relation dbr:Lexicographic_order dbr:Commutative_property dbr:Isomorphic dbr:Unicode_equivalence dbc:Semigroup_theory dbr:Semigroup
dbo:wikiPageExternalLink
n10:cartfoa.html n17:diekert97partial.html
owl:sameAs
n9:33fVb freebase:m.02qnr3g wikidata:Q3321292 dbpedia-fr:Monoïde_des_traces yago-res:Trace_monoid
dbp:wikiPageUsesTemplate
dbt:Citation dbt:Non-sequitur dbt:Expand_section dbt:Isbn dbt:Short_description dbt:Reflist
dbp:postText
See Talk:Trace monoid#As Syntactic Monoids
dbp:date
April 2022
dbo:abstract
In computer science, a trace is a set of strings, wherein certain letters in the string are allowed to commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order, but allowing certain reshufflings to take place. Traces were introduced by Pierre Cartier and Dominique Foata in 1969 to give a combinatorial proof of MacMahon's master theorem. Traces are used in theories of concurrent computation, where commuting letters stand for portions of a job that can execute independently of one another, while non-commuting letters stand for locks, synchronization points or thread joins. The trace monoid or free partially commutative monoid is a monoid of traces. In a nutshell, it is constructed as follows: sets of commuting letters are given by an independency relation. These induce an equivalence relation of equivalent strings; the elements of the equivalence classes are the traces. The equivalence relation then partitions up the free monoid (the set of all strings of finite length) into a set of equivalence classes; the result is still a monoid; it is a quotient monoid and is called the trace monoid. The trace monoid is universal, in that all dependency-homomorphic (see below) monoids are in fact isomorphic. Trace monoids are commonly used to model concurrent computation, forming the foundation for process calculi. They are the object of study in trace theory. The utility of trace monoids comes from the fact that they are isomorphic to the monoid of dependency graphs; thus allowing algebraic techniques to be applied to graphs, and vice versa. They are also isomorphic to history monoids, which model the history of computation of individual processes in the context of all scheduled processes on one or more computers. En mathématiques et en informatique, une trace est un ensemble de mots, où certaines lettres peuvent commuter, et d'autres non. Le monoïde des traces oumonoïde partiellement commutatif libre est le monoïde quotient dumonoïde libre par une relation de commutation de lettres. Le monoïdedes traces est donc une structure qui se situe entre le monoïde libreet le monoïde commutatif libre. L'intérêt mathématique du monoïde des traces a été mis en évidencedans l'ouvrage fondateur . Les traces apparaissent dans la modélisation en programmation concurrente, où les lettres qui peuvent commuter représentent des parties de processus qui peuvent s'exécuter de façon indépendante, alors que les lettres qui ne commutent pas représentent des verrous, leur synchronisation ou l'union de threads. Ce modèle a été proposé dans .
gold:hypernym
dbr:Set
prov:wasDerivedFrom
wikipedia-en:Trace_monoid?oldid=1118361208&ns=0
dbo:wikiPageLength
11270
foaf:isPrimaryTopicOf
wikipedia-en:Trace_monoid