On Non-overlapping Words
Summary :
Let Q be the set of all primitive words over a finite alphabet having at least two letters. In this paper, we study the language D(1) of all non-overlapping (d-primitive) words, which is a proper subset of Q. We show that D(1) is a context-sensitive langauage but not a deterministic context-free language. Further it is shown that [D(1)]n is not regular for n ≥ 1.
- Publication
- IEICE TRANSACTIONS on Information Vol.E94-D No.3 pp.707-709
- Publication Date
- 2011/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E94.D.707
- Type of Manuscript
- LETTER
- Category
- Fundamentals of Information Systems
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tetsuo MORIYA, Itaru KATAOKA, "On Non-overlapping Words" in IEICE TRANSACTIONS on Information,
vol. E94-D, no. 3, pp. 707-709, March 2011, doi: 10.1587/transinf.E94.D.707.
Abstract: Let Q be the set of all primitive words over a finite alphabet having at least two letters. In this paper, we study the language D(1) of all non-overlapping (d-primitive) words, which is a proper subset of Q. We show that D(1) is a context-sensitive langauage but not a deterministic context-free language. Further it is shown that [D(1)]n is not regular for n ≥ 1.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.707/_p
Copy
@ARTICLE{e94-d_3_707,
author={Tetsuo MORIYA, Itaru KATAOKA, },
journal={IEICE TRANSACTIONS on Information},
title={On Non-overlapping Words},
year={2011},
volume={E94-D},
number={3},
pages={707-709},
abstract={Let Q be the set of all primitive words over a finite alphabet having at least two letters. In this paper, we study the language D(1) of all non-overlapping (d-primitive) words, which is a proper subset of Q. We show that D(1) is a context-sensitive langauage but not a deterministic context-free language. Further it is shown that [D(1)]n is not regular for n ≥ 1.},
keywords={},
doi={10.1587/transinf.E94.D.707},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - On Non-overlapping Words
T2 - IEICE TRANSACTIONS on Information
SP - 707
EP - 709
AU - Tetsuo MORIYA
AU - Itaru KATAOKA
PY - 2011
DO - 10.1587/transinf.E94.D.707
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E94-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2011
AB - Let Q be the set of all primitive words over a finite alphabet having at least two letters. In this paper, we study the language D(1) of all non-overlapping (d-primitive) words, which is a proper subset of Q. We show that D(1) is a context-sensitive langauage but not a deterministic context-free language. Further it is shown that [D(1)]n is not regular for n ≥ 1.
ER -
English
