uf14.pdf (262.53 kB)
Download file

Factorization in formal languages

Download (262.53 kB)
conference contribution
posted on 25.09.2015, 08:48 authored by Paul Bell, Daniel Reidenbach, J.O. Shallit
We consider several language-theoretic aspects of unique factorization in formal languages. We reprove the familiar fact that the set uf(L) of words having unique factorization into elements of L is regular if L is regular, and from this deduce an quadratic upper and lower bound on the length of the shortest word not in uf(L). We observe that uf(L) need not be context-free if L is context-free. Next, we consider some variations on unique factorization. We de ne a notion of \semi-unique" factorization, where every factorization has the same number of terms, and show that, if L is regular or even nite, the set of words having such a factorization need not be context-free. Finally, we consider additional variations, such as unique factorization \up to permutation" and \up to subset". Although all these variations have been considered before, it appears that the languages of words having these properties have not been positioned in the Chomsky hierarchy up to now. We also consider the length of the shortest word not having the desired property.

History

School

  • Science

Department

  • Computer Science

Published in

Developments in Language Theory

Volume

9168

Issue

1

Pages

97 - 107 (11)

Citation

BELL, P.C., REIDENBACH, D. and SHALLIT, J.O., 2015. Factorization in formal languages. IN: Potapov, I (ed). 19th International Conference on Developments in Language Theory, Liverpool, UK, 27-30 July, pp. 97 - 107

Publisher

© Springer International Publishing

Version

AM (Accepted Manuscript)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/

Publication date

2015

Notes

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-21500-6

ISBN

978-3-319-21500-6;978-3-319-21499-3

Book series

Lecture Notes in Computer Science;9168

Language

en

Location

Liverpool, UK

Usage metrics

Keywords

Exports