On avoidability of formulas with reversal

DOI10.1051/ITA/2017013zbMATH Open1390.68512arXiv1703.10522OpenAlexW3099621745MaRDI QIDQ4638263FDOQ4638263

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)

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$).

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

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

zbMATH Keywords

pattern avoidanceunavoidabilityformula with reversal

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Avoidable patterns in strings of symbols
• Avoidability index for binary patterns with reversal
• BLOCKING SETS OF TERMS
• Title not available (Why is that?)
• A proof of Dejean’s conjecture
• Last cases of Dejean's conjecture
• A family of formulas with reversal of high avoidability index

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)