On Collapsing Prefix Normal Words

Pamela Fleischmann*, Mitja Kulczynski, Dirk Nowotka, Danny Bøgsted Poulsen

*Kontaktforfatter

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

2 Citationer (Scopus)

Abstrakt

Prefix normal words are binary words in which each prefix has at least the same number of 1 s as any factor of the same length. Firstly introduced in 2011, the problem of determining the index (amount of equivalence classes for a given word length) of the prefix normal equivalence relation is still open. In this paper, we investigate two aspects of the problem, namely prefix normal palindromes and so-called collapsing words (extending the notion of critical words). We prove characterizations for both the palindromes and the collapsing words and show their connection. Based on this, we show that still open problems regarding prefix normal words can be split into certain subproblems.
OriginalsprogEngelsk
TitelLanguage and Automata Theory and Applications : 14th International Conference, LATA 2020, Milan, Italy, March 4–6, 2020, Proceedings
RedaktørerAlberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron
Antal sider13
ForlagSpringer
Publikationsdato2020
Sider412-424
ISBN (Trykt)978-3-030-40607-3
ISBN (Elektronisk)978-3-030-40608-0
DOI
StatusUdgivet - 2020
Begivenhed14th International Conference on Language and Automata Theory and Applications - Milano, Italien
Varighed: 4 mar. 20206 mar. 2020
Konferencens nummer: 14

Konference

Konference14th International Conference on Language and Automata Theory and Applications
Nummer14
LandItalien
ByMilano
Periode04/03/202006/03/2020
NavnLecture Notes in Computer Science (LNCS)
Vol/bind12038
ISSN0302-9743

Fingeraftryk Dyk ned i forskningsemnerne om 'On Collapsing Prefix Normal Words'. Sammen danner de et unikt fingeraftryk.

Citationsformater