On avoidability of formulas with reversal

DOI10.1051/ITA/2017013MaRDI QIDQ4638263zbMATH OpenOpenAlexFDO

Authors Narad Rampersad, James D. Currie, L. A. S. Mól

Publication date 4 May 2018

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.10522

zbMATH Keywords

pattern avoidanceunavoidabilityformula with reversal

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: While a characterization of unavoidable formulas (without reversal) is well-known, little is known about the avoidability of formulas with reversal in general. In this article, we characterize the unavoidable formulas with reversal that have at most two one-way variables ($x$ is a one-way variable in formula with reversal $phi$ if exactly one of $x$ and $x^R$ appears in $phi$).

Recommendations

• Avoidance bases for formulas with reversal
• A family of formulas with reversal of arbitrarily high avoidability index
• Avoidability of circular formulas
• A family of formulas with reversal of high avoidability index
• scientific article; zbMATH DE number 1972804
• Avoidability of formulas with two variables
• Avoidability of formulas with two variables
• The complexity of satisfaction problems in reverse mathematics
• The Complexity of Satisfaction Problems in Reverse Mathematics
• Reverse mathematics and uniformity in proofs without excluded middle

Cites work

• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• A family of formulas with reversal of high avoidability index
• A proof of Dejean’s conjecture
• Avoidability index for binary patterns with reversal
• Avoidable patterns in strings of symbols
• BLOCKING SETS OF TERMS
• Last cases of Dejean's conjecture

Cited in

(6)

• On some properties of reverse Polish notation
• A family of formulas with reversal of high avoidability index
• Formulas with reversal
• Avoidance bases for formulas with reversal
• Reverse formalism 16
• A family of formulas with reversal of arbitrarily high avoidability index

This page was built for publication: On avoidability of formulas with reversal

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