About: We present some asymptotic properties on the average number of prefixes in trace languages. Such languages are characterized by an alphabet and a set of commutation rules, also called concurrent alphabet, which can be encoded by an independency graph or by its complement, called dependency graph. One key technical result, which has its own interest, concerns general properties of graphs and states that “if an undirected graph admits a transitive orientation, then the multiplicity of the root of minimum modulus of its clique polynomial is smaller or equal to the number of connected components of its complement graph”. As a consequence, under the same hypothesis of transitive orientation of the independency graph, one obtains the relation [Formula: see text], where the random variables [Formula: see text] and [Formula: see text] represent the number of prefixes in traces of length n under two different fundamental probabilistic models: the uniform distribution among traces of length n (for [Formula: see text]), the uniform distribution among words of length n (for [Formula: see text]). These two quantities are related to the time complexity of algorithms for solving classical membership problems on trace languages.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • We present some asymptotic properties on the average number of prefixes in trace languages. Such languages are characterized by an alphabet and a set of commutation rules, also called concurrent alphabet, which can be encoded by an independency graph or by its complement, called dependency graph. One key technical result, which has its own interest, concerns general properties of graphs and states that “if an undirected graph admits a transitive orientation, then the multiplicity of the root of minimum modulus of its clique polynomial is smaller or equal to the number of connected components of its complement graph”. As a consequence, under the same hypothesis of transitive orientation of the independency graph, one obtains the relation [Formula: see text], where the random variables [Formula: see text] and [Formula: see text] represent the number of prefixes in traces of length n under two different fundamental probabilistic models: the uniform distribution among traces of length n (for [Formula: see text]), the uniform distribution among words of length n (for [Formula: see text]). These two quantities are related to the time complexity of algorithms for solving classical membership problems on trace languages.
Subject
  • Graph theory
  • Graph families
  • Order theory
  • Directed graphs
  • Application-specific graphs
  • Perfect graphs
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software