Биекция между словами и матрицами

[alcoholist]

то есть не любую матрицу можно допустимым словом записать?

[situs]

Записать то можно, думаю, любую. Но ведь может быть такое, что одной матрице соответствуют два разных допустимых слова. Или Вы про другое говорите?

-- 03.03.2019, 22:17 --

Подумал еще. Биекция будет!

У меня же слова в некоторых случаях можно редуцировать.

Правила редукции такие:
1) Две стоящие рядом одинаковые буквы можно удалить.
2) Если буквы в слове расположены таким образом - $\dots xy \dots yx \dots$, то разрешено эти две буквы заменить на одну.

Получается, допустимых слов в алфавите из двух символов - три - $(abab), (aabb), (abba)$. Cлова $(aabb)$ и $(abba)$ редуцируются до одного пустого (нулевого). В итоге получается два слова - $ (abab)$ и пустое. Им соответствуют ровно две матрицы. Одна нулевая и другая с единицами вне диагонали.

alcoholist в сообщении #1379638 писал(а):

можно выбрать определенным образом слово "наименьшего веса"

Это Вы про это?

[alcoholist]

situs в сообщении #1379669 писал(а):

Это Вы про это?

вроде того... Но биективность при данных правилах редукции надо доказывать

[situs]

Спасибо!

Можете дать намек или ссылку, как это правильно делать?

[waxtep]

situs в сообщении #1379669 писал(а):

2) Если буквы в слове расположены таким образом - $\dots xy \dots yx \dots$, то разрешено эти две буквы заменить на одну.

А какие две буквы можно заменить и на какую одну? Букв тут четыре, читается неоднозначно.
И еще вопрос: в алфавите из трех символов слово $bacbac$ является допустимым? А $cabcab$? Или же всегда первый символ допустимого слова - $a$?

[alcoholist]

situs в сообщении #1379669 писал(а):

2) Если буквы в слове расположены таким образом - $\dots xy \dots yx \dots$, то разрешено эти две буквы заменить на одну.

?

[situs]

waxtep в сообщении #1379700 писал(а):

situs в сообщении #1379669 писал(а):

2) Если буквы в слове расположены таким образом - $\dots xy \dots yx \dots$, то разрешено эти две буквы заменить на одну.

А какие две буквы можно заменить и на какую одну? Букв тут четыре, читается неоднозначно.

Буквы же две - $x, y$. Только каждая встречается ровно 2 раза. Если буквы в слове расположены таким образом - $\dots xy \dots yx \dots$, то разрешено эти две буквы заменить на одну, т.е. строка преобразуется к виду $\dots x' \dots x' \dots$

Цитата:

И еще вопрос: в алфавите из трех символов слово $bacbac$ является допустимым? А $cabcab$? Или же всегда первый символ допустимого слова - $a$?

Первоначально всегда $a$. Но в результате преобразований, например слова $aabcbc$ у вас получится слово $bcbc$. Тогда можно переименовать буквы $bcbc$ в $abab$. То есть, как обозначаются буквы не важно. Важен только их порядок расположения в строке.

[bot]

(Оффтоп)

[off]

situs в сообщении #1379669 писал(а):

2) Если буквы в слове расположены таким образом - $\dots xy \dots yx \dots$, то разрешено эти две буквы заменить на одну.

Это как? Режем букву пополам и вставляем половинки вместо $xy $ и $yx$? А с дружбой как?

[/off]

situs в сообщении #1379669 писал(а):

Правила редукции такие:

Откуда взялись такие правила? Это Вы сами придумали, пытаясь формализовать задачу? Какую - как она выглядела при рождении?

[alcoholist]

situs в сообщении #1379742 писал(а):

т.е. строка преобразуется к виду $\dots x' \dots x' \dots$

и как теперь матрицу рисовать?

-- Пн мар 04, 2019 10:56:09 --

situs
Для построения матрицы важно лишь отношение дружественности. Если оно задается именно так:

situs в сообщении #1379624 писал(а):

Теперь, пусть дано допустимое слово $w$. Будем называть буквы $x$ и $y$ в слове $w$ дружественными тогда и только тогда, когда они расположены в таком порядке - $\dots x \dots y \dots x \dots y$

то какие матрицы можно при этом получить? Неужели только ранга $\le 2$?

[situs]

alcoholist в сообщении #1379745 писал(а):

situs в сообщении #1379742 писал(а):

т.е. строка преобразуется к виду $\dots x' \dots x' \dots$

и как теперь матрицу рисовать?

Очень просто. Вот берем допустимое слово $abcdacbd$. Редуцируем его до $ab'dab'd$. Если переименовать буквы, то это то же самое, что и $abcabc$ с матрицей

$\mathbf{M}(xyzxyz) = \bordermatrix{ & x & y & z\cr x & 0 & 1 & 1\cr y & 1 & 0 & 1 \cr z & 1 & 1 & 0 \cr}$

-- 04.03.2019, 11:09 --

Если что, то ранг этой матрицы над $\mathbb{Z}_2$ не более 2.

[alcoholist]

situs в сообщении #1379747 писал(а):

Если что, то ранг этой матрицы над $\mathbb{Z}_2$ не более 2.

ранг этой матрицы равен 2
А для произвольного слова? Например, $abcdcdab$?

[situs]

alcoholist в сообщении #1379749 писал(а):

А для произвольного слова?

Для произвольного слова я этого не утверждал. Может быть и больше. Всегда кратен двум.

situs в сообщении #1379651 писал(а):

Я доказываю теорему в которой утверждается, что "слово является хорошим тогда и только тогда, когда ранг матрицы слова $\leqslant 2$". Думаю, что биекция нужна для доказательства части "только тогда".

[alcoholist]

слово

alcoholist в сообщении #1379749 писал(а):

$abcdcdab$

является хорошим, а ранг соответствующей матрицы равен 4, нет?

[situs]

alcoholist в сообщении #1379755 писал(а):

является хорошим, а ранг соответствующей матрицы равен 4

Вы правы, слово не хорошее. Ранг равен 4.

[alcoholist]

situs в сообщении #1379756 писал(а):

слово не хорошее

Но оно удовлетворяет всем вашим вышеописанным требованиям. Все-таки вы сами не определились с тем, какие слова называются допустимыми (хорошими). Уже дайте внятное определение.