Combinatorics on Words Basics

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F21%3A00353328" target="_blank" >RIV/68407700:21240/21:00353328 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/21:10438501

Výsledek na webu

<a href="https://www.isa-afp.org/entries/Combinatorics_Words.html" target="_blank" >https://www.isa-afp.org/entries/Combinatorics_Words.html</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Combinatorics on Words Basics

Popis výsledku v původním jazyce

We formalize basics of Combinatorics on Words. This is an extension of existing theories on lists. We provide additional properties related to prefix, suffix, factor, length and rotation. The topics include prefix and suffix comparability, mismatch, word power, total and reversed morphisms, border, periods, primitivity and roots. We also formalize basic, mostly folklore results related to word equations: equidivisibility, commutation and conjugation. Slightly advanced properties include the Periodicity lemma (often cited as the Fine and Wilf theorem) and the variant of the Lyndon-Schützenberger theorem for words. We support the algebraic point of view which sees words as generators of submonoids of a free monoid. This leads to the concepts of the (free) hull, the (free) basis (or code).

Název v anglickém jazyce

Combinatorics on Words Basics

Popis výsledku anglicky

We formalize basics of Combinatorics on Words. This is an extension of existing theories on lists. We provide additional properties related to prefix, suffix, factor, length and rotation. The topics include prefix and suffix comparability, mismatch, word power, total and reversed morphisms, border, periods, primitivity and roots. We also formalize basic, mostly folklore results related to word equations: equidivisibility, commutation and conjugation. Slightly advanced properties include the Periodicity lemma (often cited as the Fine and Wilf theorem) and the variant of the Lyndon-Schützenberger theorem for words. We support the algebraic point of view which sees words as generators of submonoids of a free monoid. This leads to the concepts of the (free) hull, the (free) basis (or code).

Druh

J_ost - Ostatní články v recenzovaných periodicích

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA20-20621S" target="_blank" >GA20-20621S: Formalizace kombinatoriky na slovech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Archive of Formal Proofs

ISSN

2150-914X

e-ISSN

2150-914X

Svazek periodika

—

Číslo periodika v rámci svazku

May

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

135

Strana od-do

—

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—