On avoidability of formulas with reversal

Thumbnail

View Open

Metadata

Show full item record

Author

Currie, James D.
Mol, Lucas
Rampersad, Narad

Uri

http://hdl.handle.net/10680/1834

Date

2018-02-13

Doi

https://doi.org/10.1051/ita/2017013

Citation

James D. Currie, Lucas Mol, and Narad Rampersad. "On avoidability of formulas with reversal." RAIRO - Theoretical Informatics and Applications / Informatique Théorique et Applications 51(4) (2017): 181-189. DOI: 10.1051/ita/2017013.

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 φ if exactly one of x and x^R appears in φ).

Collections