Generalized pattern matching and the complexity of unavoidability testing

DOI10.1007/3-540-48194-X_20MaRDI QIDQ4547752zbMATH OpenFDO

Authors Christine E. Heitsch

Publication date 21 August 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2089/20890219

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Recommendations

• Insufficiency of four known necessary conditions on string unavoidability
• On long words avoiding Zimin patterns
• On Long Words Avoiding Zimin Patterns
• Tower-type bounds for unavoidable patterns in words
• Testing avoidability on sets of partial words is hard

Cited in

(2)

• The complexity of unavoidable word patterns
• Insufficiency of four known necessary conditions on string unavoidability

This page was built for publication: Generalized pattern matching and the complexity of unavoidability testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4547752)