Строки в математике

[Mr. Dred]

Здравствуйте, знает ли кто-нибудь как называется область математики, объектом исследований которой являются строки. Может есть какая-нибудь особая алгебра строк?

[Joker_vD]

Строки? Э-э-э... просто строки? Есть математическая логика. Есть теория автоматов. То, что они изучают, вполне подходит под определение строк.

[Утундрий]

А в математике (sic!) есть что-то, чего нельзя расписать в строку?

[Mr. Dred]

Просто есть новый подход к исследованию строк, разработанный доцентом в нашем ВУЗе, я хочу понять можно ли найти взаимосвязи с другими областями математики объектом которых являются строки.
Суть подхода в исследовании строк с спомощью интервалов (расстояний в символах между одинаковыми компонентами) между компонентами строки.

[Joker_vD]

Навскидку вспоминается только метод Казиски для взлома шифра Вижинера Ваш доцент точно сам придумал свой метод?

[Mr. Dred]

Думаю что да, но в истории математики столько случаев изобретений велосипеда, что и ваш вариант не исключение ))
Вообще суть метода еще и в возможности вычисления новых характеристик текста, аналога информационной энтропии, только вместо частот берутся интервалы.
$g=\frac{1}{n}\log_2 \Delta_{ij}$
где $\Delta_{ij}$ - интервал между $i$-м и $i+1$-м вхождением $j$-ого символа
$g$ - удаленность знаковой цепи

В сравнении например с подходом на основе вероятностей вхождений символов, удаленность дает совершенно другую, дополнительную информацию о строке

[Утундрий]

Mr. Dred в сообщении #487447 писал(а):

Суть подхода в исследовании строк с спомощью интервалов (расстояний в символах между одинаковыми компонентами) между компонентами строки.

Исследование того, что по самой своей природе является дитём одной лишь договорённости? Ну, пуркуа бы и не па? Можно и фигуру цапф большого пассажного инструмента со всем рвением изучать, при наличии желания и бездны свободного времени.

[Sonic86]

Mr. Dred в сообщении #487436 писал(а):

Здравствуйте, знает ли кто-нибудь как называется область математики, объектом исследований которой являются строки. Может есть какая-нибудь особая алгебра строк?

Есть свободные полугруппы и уравнения в них. Элементы свободных полугрупп - это строки, а полугрупповая операция - конкатенация. Сразу можете нагуглить статьи Маканина о разрешимости классов некоторых уравнений в полугруппах. И вообще - ключевые слова "уравнения в свободной полугруппе". Они тесно связаны с уравнениями в свободной группе, а там уж и до проблем равенства слов недалеко. Но это такие суровые вещи, с матлогикой связано даже.

Литературу именно об этом не скажу. Есть книги по комбинаторной теории групп (Линдон, Шупп ; Магнус, Каррас, Солитэр) - но то ли это, что Вам нужно?....

(Оффтоп)

Почему-то еще не встречал в полугруппах такие функции, как аналоги SQL - substr, instr, replace и т.п., только длина есть - дельфины и мускульщики тут уже продвинулись дальше Мне бы вот математическое обозначение substr прямо сейчас очень бы пригодилось

[Mr. Dred]

Спасибо большое, именно это я и искал!

[Sonic86]

Mr. Dred в сообщении #487447 писал(а):

Просто есть новый подход к исследованию строк, разработанный доцентом в нашем ВУЗе, я хочу понять можно ли найти взаимосвязи с другими областями математики объектом которых являются строки.
Суть подхода в исследовании строк с помощью интервалов (расстояний в символах между одинаковыми компонентами) между компонентами строки.

Может что-то поконкретнее скажете.
Проблемы там можете также нагуглить...

[Mr. Dred]

Sonic86 в сообщении #487462 писал(а):

Mr. Dred в сообщении #487447 писал(а):

Просто есть новый подход к исследованию строк, разработанный доцентом в нашем ВУЗе, я хочу понять можно ли найти взаимосвязи с другими областями математики объектом которых являются строки.
Суть подхода в исследовании строк с помощью интервалов (расстояний в символах между одинаковыми компонентами) между компонентами строки.

Может что-то поконкретнее скажете.
Проблемы там можете также нагуглить...

Если поконкретнее, то подход используется для вычисления характеристик строк
Например в биоинформатике и мат. лингвистике как основа для меры растояния между строками

Основная характеристика описана вот в этом сообщении

Mr. Dred в сообщении #487451 писал(а):

Вообще суть метода еще и в возможности вычисления новых характеристик текста, аналога информационной энтропии, только вместо частот берутся интервалы.
$g=\frac{1}{n}\log_2 \Delta_{ij}$
где $\Delta_{ij}$ - интервал между $i$-м и $i+1$-м вхождением $j$-ого символа
$g$ - удаленность знаковой цепи

В сравнении например с подходом на основе вероятностей вхождений символов, удаленность дает совершенно другую, дополнительную информацию о строке

Основной проблемой, как мне кажется является не совсем понятная математическая природа интервалов, если в теории вероятности из смысла вероятности достаточно очевидно вытекают свойства последней и опрерации в вероятностном пространстве, то с интервалами дело обстоит значительно хуже.

[Sonic86]

Mr. Dred в сообщении #487475 писал(а):

Основная характеристика описана вот в этом сообщении

Тогда то, что я Вам сказал - это не то. Это Вам надо какие-то статьи искать на эту тему из теорвера.

[Kallikanzarid]

Mr. Dred
Свободные магмы не подходят?

[Mr. Dred]

Kallikanzarid в сообщении #487548 писал(а):

Mr. Dred
Свободные магмы не подходят?

Гуглил, но в интернете по свободным магмам информации совсем мало, можете подсказать что-либо из литературы?

[arseniiv]

Свободные магмы не должны ли быть более общими, чем надо чем свободные полугруппы? На самом деле, конкатенация ассоциативна, так что алгебра строк будет полугруппой. А если туда включена пустая строка, то ещё и моноидом, потому что пустая строка, прибавляй её справа или слева, даст ту же строку, к которой прибавляли. А магма никаких требований к операции своей не просит, так что слишком обща.

-- Пт сен 30, 2011 00:26:04 --

(Оффтоп)

Sonic86 в сообщении #487460 писал(а):

Мне бы вот математическое обозначение substr прямо сейчас очень бы пригодилось

Неужели совсем не встречали? Ну вот. Я думал, разные алгоритмоизобретатели уже постарались над этим…

Давайте создадим тему, может, кто-то знает? Или хотя бы обсуждать там, какие обозначения были бы хорошими, а какие не очень.