𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generalized factorizations of words and their algorithmic properties

✍ Scribed by Juhani Karhumäki; Wojciech Plandowski; Wojciech Rytter

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
837 KB
Volume
218
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We formalize the notion of a factorization of a word, a so-called S-factorization, introduced in [7] when solving some open problems on word equations. We show that most of the factorizations considered in the literature fit well into that framework, and in particular that central algorithmic problems, such as the uniqueness or the synchronizability, remain polynomial time solvable for an important and large class of Sfactorizations, namely for regular F-factorizations.

📜 SIMILAR VOLUMES

Generalized Transition Waves and Their P
Generalized Transition Waves and Their Properties
✍ Henri Berestycki; François Hamel 📂 Article 📅 2012 🏛 John Wiley and Sons 🌐 English ⚖ 428 KB

## Abstract In this paper, we generalize the usual notions of waves, fronts, and propagation speeds in a very general setting. These new notions, which cover all usual situations, involve uniform limits, with respect to the geodesic distance, to a family of hypersurfaces that are parametrized by ti

Factorizations of complete multipartite
Factorizations of complete multipartite graphs into generalized cubes
✍ El--Zanati, S.; Vanden Eynden, C. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 2 views

For a positive integer d, the usual d-dimensional cube Q d is defined to be the graph (K 2 ) d , the Cartesian product of d copies of K 2 . We define the generalized cube Q(K k , d) to be the graph (K k ) d for positive integers d and k. We investigate the decomposition of the complete multipartite