Probabilistic estimation of the number of prefixes of a trace (Q1184996)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Probabilistic estimation of the number of prefixes of a trace |
scientific article |
Statements
Probabilistic estimation of the number of prefixes of a trace (English)
0 references
28 June 1992
0 references
Asymptotic estimations of the number of prefixes of elements of free partially commutative monoids are carried out. The results are used to determine the probabilistic complexity of some combinatorial algorithms for trace languages, as, for example, the complexity of solving the membership problem for regular and context-free trace languages.
0 references
probabilistic complexity
0 references
combinatorial algorithms for trace languages
0 references
0 references
