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

[Circiter]

2Mr. Dred

Цитата:

как называется область математики, объектом исследований которой являются строки.

Формальные языки и грамматики.

Цитата:

Может есть какая-нибудь особая алгебра строк?

Есть такая алгебра строк (string algebra); к теме отношение имеет, но наверное не самое прямое. А так смотрите регулярные выражения, алгебра Клини, ну и в таком духе.

Цитата:

Вообще суть метода еще и в возможности вычисления новых характеристик текста, аналога информационной энтропии, только вместо частот берутся интервалы.

В голове вертятся всякие глупости вроде автокорреляции и т.д. и т.п. :) Вообще, мне кажется, что такие задачки погружаемы в фреймворк теории обработки сигналов. Интервалы, частоты, и пр. -- это же все типичные кандидаты для гармонического анализа или чего-то подобного (Фурье, вейвлеты). По спектру можно какие-нибудь энергетические характеристики посчитать, аналогичные вашей "удаленности"... Это я к тому, что, возможно, существуют аналоги таких характеристик текста, но в "неожиданных" областях знаний (например, в сжатии данных). А спонтанно в голову никакие конкретные аналогии что-то не приходят -- в этом смысле, затея, видимо, не пустая.

[Kallikanzarid]

arseniiv в сообщении #487815 писал(а):

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

Да, вы правы :)

[Sonic86]

(Оффтоп)

arseniiv в сообщении #487815 писал(а):

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

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

Да я не так много читал на эту тему. Там обычно с группами разбираются детально, а сами строки их особо не интересуют.

[Kallikanzarid]

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

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

А зачем? Соответствующие алгоритмы элементарны.

-- Пт сен 30, 2011 12:15:26 --

Ну давайте попробуем: пусть $S$ - свободный моноид. Определим $f(u, v)x$ как функцию, заменяющую каждое вхождение $u$ в $x$ на $v$. Легко показать, что $f$ не является морфизмом моноидов, например для латинского алфавита $f(mom, dad)(mommo) f(mom, dad)(mmom) = dadmomdad$, а $f(mom, dad)(mommommom) = daddaddad$.

[Sonic86]

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

А зачем? Соответствующие алгоритмы элементарны.

-- Пт сен 30, 2011 12:15:26 --

Ну давайте попробуем: пусть $S$ - свободный моноид. Определим $f(u, v)x$ как функцию, заменяющую каждое вхождение $u$ в $x$ на $v$. Легко показать, что $f$ не является морфизмом моноидов, например для латинского алфавита $f(mom, dad)(mommo) f(mom, dad)(mmom) = dadmomdad$, а $f(mom, dad)(mommommom) = daddaddad$.

Да я не про это Понятно, что это просто и понятно. Просто в литературе обозначений не видел, хотя неявно их используют. Просто они на это не обращают внимания - они его больше на группах акцентируют.

[Kallikanzarid]

Sonic86
Меня как раз смущает, что эта функция не является морфизмом - значит, категория моноидов для работы со строками подходит намного меньше, чем я думал.

[arseniiv]

(Оффтоп)

А с чего ей надо быть морфизмом?

[Kallikanzarid]

arseniiv в сообщении #488076 писал(а):

А с чего ей надо быть морфизмом?

Потому что мы обычно хотим, чтобы интересные нам операции были морфизмами, функторами, естественными преобразованиями и т. д., иначе теория получается нехорошей.

[Joker_vD]

Kallikanzarid
А как быть, например, с алгебраическим замыканием поля? Я сомневаюсь, что оно является универсальным объектом в какой-то категории — у него автоморфизмов до черта...

[Kallikanzarid]

Joker_vD
Ну да :) Тут уже играет свою роль сохранение нетривиальности, а не негодность категории полей, ИМХО.