Probabilistic estimation of the number of prefixes of a trace (Q1184996)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Probabilistic estimation of the number of prefixes of a trace |
scientific article; zbMATH DE number 35430
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Probabilistic estimation of the number of prefixes of a trace |
scientific article; zbMATH DE number 35430 |
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
