Factorization in formal languages

DOI10.1007/978-3-319-21500-6_7MaRDI QIDQ3451092zbMATH OpenOpenAlexFDO

Authors Paul C. Bell, Daniel Reidenbach, Jeffrey Shallit

Publication date 10 November 2015

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.06365, https://dspace.lboro.ac.uk/2134/18859

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

Abstract: We consider several novel 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 variations on unique factorization. We define a notion of "semi-unique" factorization, where every factorization has the same number of terms, and show that, if L is regular or even finite, 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".

Recommendations

• Unique decipherability in formal languages
• ON LANGUAGES FACTORIZING THE FREE MONOID
• On some factorization problems
• Prime Decompositions of Regular Languages
• A UNIQUE DECOMPOSITION THEOREM FOR FACTORIAL LANGUAGES

Cites work

• A note on multiset decipherable codes
• A Second Course in Formal Languages and Automata Theory
• Automata, Boolean matrices, and ultimate periodicity.
• Codes and automata.
• Coding partitions
• Deciding multiset decipherability
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 826059 (Why is no real title available?)
• Inverse star, borders, and palstars
• Multiset and set decipherable codes
• Nondeterministic Space is Closed under Complementation
• On multiset decipherable codes (Corresp.)
• The finest homophonic partition and related code concepts

Cited in

(2)

• On intermediate factorial languages
• Unique decipherability in formal languages

This page was built for publication: Factorization in formal languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3451092)