On avoidability of formulas with reversal
| Autor: | Narad Rampersad, James D. Currie, Lucas Mol |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Pure mathematics
General Mathematics 010102 general mathematics 0102 computer and information sciences Formula with reversal 68R15 Characterization (mathematics) 01 natural sciences Computer Science Applications 010201 computation theory & mathematics Pattern avoidance FOS: Mathematics Mathematics - Combinatorics Unavoidability Combinatorics (math.CO) 0101 mathematics Software Mathematics Variable (mathematics) |
| Popis: | 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$). Comment: 14 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|