Balanced word: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
A [[word]] or [[necklace]] ''s'' is '''balanced''' if its '''block balance''' satisfies the following: | A [[word]] or [[necklace]] ''s'' is '''balanced''' if its '''block balance'''{{idiosyncratic}} satisfies the following: | ||
<math> \mathsf{block\_balance}(s) := \max \big\{ \big| |w|_{x_i} - |w'|_{x_i} \big| : x_i \text{ is a letter of }s\text{ and }k = \operatorname{len}(w) = \operatorname{len}(w') \big\} \leq 1,</math> | <math> \mathsf{block\_balance}(s) := \max \big\{ \big| |w|_{x_i} - |w'|_{x_i} \big| : x_i \text{ is a letter of }s\text{ and }k = \operatorname{len}(w) = \operatorname{len}(w') \big\} \leq 1,</math> | ||
where |''u''|<sub>''x''<sub>''i''</sub></sub> is the number of occurrences of the letter ''x''<sub>''i''</sub> in the word ''u''. | where |''u''|<sub>''x''<sub>''i''</sub></sub> is the number of occurrences of the letter ''x''<sub>''i''</sub> in the word ''u''. | ||
== Properties == | == Properties == | ||
| Line 16: | Line 14: | ||
== Generalizations == | == Generalizations == | ||
# If <math> \mathsf{block\_balance}(s) \leq m,</math> then we say that ''s'' is ''m''-'''block-balanced'''{{idiosyncratic}}. | |||
# The following stronger property implies but is not equivalent to ''m''-block-balancedness: For every letter ''a'' in ''s'' and every factor of the form ''awa'', any factor ''w' '' in ''s'' such that len(<i>w'</i>) = len(''w'') + ''m'' + 1 satisfies |<i>w'</i>|<sub>a</sub> ≥ |''w''|<sub>a</sub> + 1.<ref>Sano, S., Miyoshi, N., & Kataoka, R. (2004). m-Balanced words: A generalization of balanced words. Theoretical computer science, 314(1-2), 97-120.</ref> | |||
== References == | == References == | ||
[[Category:Scale]][[Category:Terms]] | [[Category:Scale]][[Category:Terms]] | ||
[[Category:Combinatorics on words]] | [[Category:Combinatorics on words]] | ||