Probabilistic estimation of the number of prefixes of a trace

DOI10.1016/0304-3975(92)90314-6zbMath0747.68034OpenAlexW2048535897WikidataQ128022075 ScholiaQ128022075MaRDI QIDQ1184996

Massimiliano Goldwurm

Publication date: 28 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90314-6

zbMATH Keywords

combinatorial algorithms for trace languagesprobabilistic complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items

Pattern statistics and Vandermonde matrices. ⋮ The lattices of prefixes and overlaps of traces ⋮ Number of prefixes in trace monoids: clique polynomials and dependency graphs

Cites Work

• On the decidability of some problems about rational subsets of free partially commutative monoids
• Theory of traces
• Membership problems for regular and context-free trace languages
• Trace languages defined by regular string languages
• Notes on finite asynchronous automata
• Characterizations of the decidability of some problems for regular trace languages
• A review of random graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item