2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 21:34 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
то есть не любую матрицу можно допустимым словом записать?

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 21:44 
Аватара пользователя


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

-- 03.03.2019, 22:17 --

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

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

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

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

alcoholist в сообщении #1379638 писал(а):
можно выбрать определенным образом слово "наименьшего веса"
Это Вы про это?

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 23:16 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
situs в сообщении #1379669 писал(а):
Это Вы про это?

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

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение03.03.2019, 23:51 
Аватара пользователя


03/02/19
138
Спасибо!

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

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение04.03.2019, 00:42 
Аватара пользователя


07/01/16
1426
Аязьма
situs в сообщении #1379669 писал(а):
2) Если буквы в слове расположены таким образом - $\dots xy \dots yx \dots$, то разрешено эти две буквы заменить на одну.
А какие две буквы можно заменить и на какую одну? Букв тут четыре, читается неоднозначно.
И еще вопрос: в алфавите из трех символов слово $bacbac$ является допустимым? А $cabcab$? Или же всегда первый символ допустимого слова - $a$?

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение04.03.2019, 10:31 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
situs в сообщении #1379669 писал(а):
2) Если буквы в слове расположены таким образом - $\dots xy \dots yx \dots$, то разрешено эти две буквы заменить на одну.

?

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение04.03.2019, 10:46 
Аватара пользователя


03/02/19
138
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$. То есть, как обозначаются буквы не важно. Важен только их порядок расположения в строке.

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение04.03.2019, 10:51 
Заслуженный участник
Аватара пользователя


21/12/05
5904
Новосибирск

(Оффтоп)

[off]
situs в сообщении #1379669 писал(а):
2) Если буквы в слове расположены таким образом - $\dots xy \dots yx \dots$, то разрешено эти две буквы заменить на одну.

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

situs в сообщении #1379669 писал(а):
Правила редукции такие:

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

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение04.03.2019, 10:52 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
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$?

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение04.03.2019, 11:03 
Аватара пользователя


03/02/19
138
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.

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение04.03.2019, 11:12 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
situs в сообщении #1379747 писал(а):
Если что, то ранг этой матрицы над $\mathbb{Z}_2$ не более 2.

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

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение04.03.2019, 11:21 
Аватара пользователя


03/02/19
138
alcoholist в сообщении #1379749 писал(а):
А для произвольного слова?
Для произвольного слова я этого не утверждал. Может быть и больше. Всегда кратен двум.

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

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение04.03.2019, 11:24 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
слово
alcoholist в сообщении #1379749 писал(а):
$abcdcdab$
является хорошим, а ранг соответствующей матрицы равен 4, нет?

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение04.03.2019, 11:29 
Аватара пользователя


03/02/19
138
alcoholist в сообщении #1379755 писал(а):
является хорошим, а ранг соответствующей матрицы равен 4
Вы правы, слово не хорошее. Ранг равен 4.

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение04.03.2019, 11:34 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
situs в сообщении #1379756 писал(а):
слово не хорошее

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 95 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: kthxbye, Mikhail_K, Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group