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 E[Tn] = O(E[Wn]), where the random variables Tn and Wn 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 Tn), – the uniform distribution among words of length n (for Wn). These two quantities are related to the time complexity of algorithms for solving classical membership problems on trace languages.
Number of Prefixes in Trace Monoids: Clique Polynomials and Dependency Graphs / C. Banderier, M. Goldwurm (LECTURE NOTES IN COMPUTER SCIENCE). - In: Beyond the Horizon of Computability / [a cura di] M. Anselmo, G. Della Vedova, F. Manea, A. Pauly. - Prima edizione. - [s.l] : Springer, 2020. - ISBN 9783030514655. - pp. 251-263 (( Intervento presentato al 16. convegno Conference on Computability in Europe, CiE 2020 tenutosi a Fisciano nel 2020.
|Titolo:||Number of Prefixes in Trace Monoids: Clique Polynomials and Dependency Graphs|
|Parole Chiave:||Trace monoids; Clique polynomials; M¨obius functions; Automata theory; Analytic combinatorics; Patterns in words|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2020|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/978-3-030-51466-2_22|
|Tipologia:||Book Part (author)|
|Appare nelle tipologie:||03 - Contributo in volume|
File in questo prodotto:
|paper34.pdf||Post-print, accepted manuscript ecc. (versione accettata dall'editore)||Administrator Richiedi una copia|
|Banderier-Goldwurm2020_Chapter_NumberOfPrefixesInTraceMonoids.pdf||Publisher's version/PDF||Administrator Richiedi una copia|