On selection functions that do not preserve normality

Wolfgang Merkle; Jan Reimann

doi:10.1007/978-3-540-45138-9_54

On selection functions that do not preserve normality

Wolfgang Merkle, Jan Reimann

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Chapter

2 Scopus citations

Abstract

The sequence selected from a sequence R(0)R(1) . . . by a language L is the subsequence of all bits R(n + 1) such that the prefix R(0) . . . R(n) is in L. By a result of Agafonoff [1], a sequence is normal if and only if any subsequence selected by a regular language is again normal. Kamae and Weiss [11] and others have raised the question of how complex a language must be such that selecting according to the language does not preserve normality. We show that there are such languages that are only slightly more complicated than regular ones, namely, normality is neither preserved by linear languages nor by deterministic one-counter languages. In fact, for both types of languages it is possible to select a constant sequence from a normal one.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Branislav Rovan, Peter Vojtas
Publisher	Springer Verlag
Pages	602-611
Number of pages	10
ISBN (Electronic)	9783540406716
DOIs	https://doi.org/10.1007/978-3-540-45138-9_54
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2747
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-45138-9_54

Cite this

Merkle, W., & Reimann, J. (2003). On selection functions that do not preserve normality. In B. Rovan, & P. Vojtas (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 602-611). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2747). Springer Verlag. https://doi.org/10.1007/978-3-540-45138-9_54

Merkle, Wolfgang ; Reimann, Jan. / On selection functions that do not preserve normality. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Branislav Rovan ; Peter Vojtas. Springer Verlag, 2003. pp. 602-611 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{3b57db1b34554082b3da9dbdd5060732,

title = "On selection functions that do not preserve normality",

abstract = "The sequence selected from a sequence R(0)R(1) . . . by a language L is the subsequence of all bits R(n + 1) such that the prefix R(0) . . . R(n) is in L. By a result of Agafonoff [1], a sequence is normal if and only if any subsequence selected by a regular language is again normal. Kamae and Weiss [11] and others have raised the question of how complex a language must be such that selecting according to the language does not preserve normality. We show that there are such languages that are only slightly more complicated than regular ones, namely, normality is neither preserved by linear languages nor by deterministic one-counter languages. In fact, for both types of languages it is possible to select a constant sequence from a normal one.",

author = "Wolfgang Merkle and Jan Reimann",

year = "2003",

doi = "10.1007/978-3-540-45138-9_54",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "602--611",

editor = "Branislav Rovan and Peter Vojtas",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Merkle, W & Reimann, J 2003, On selection functions that do not preserve normality. in B Rovan & P Vojtas (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2747, Springer Verlag, pp. 602-611. https://doi.org/10.1007/978-3-540-45138-9_54

On selection functions that do not preserve normality. / Merkle, Wolfgang; Reimann, Jan.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Branislav Rovan; Peter Vojtas. Springer Verlag, 2003. p. 602-611 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2747).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

TY - CHAP

T1 - On selection functions that do not preserve normality

AU - Merkle, Wolfgang

AU - Reimann, Jan

PY - 2003

Y1 - 2003

N2 - The sequence selected from a sequence R(0)R(1) . . . by a language L is the subsequence of all bits R(n + 1) such that the prefix R(0) . . . R(n) is in L. By a result of Agafonoff [1], a sequence is normal if and only if any subsequence selected by a regular language is again normal. Kamae and Weiss [11] and others have raised the question of how complex a language must be such that selecting according to the language does not preserve normality. We show that there are such languages that are only slightly more complicated than regular ones, namely, normality is neither preserved by linear languages nor by deterministic one-counter languages. In fact, for both types of languages it is possible to select a constant sequence from a normal one.

AB - The sequence selected from a sequence R(0)R(1) . . . by a language L is the subsequence of all bits R(n + 1) such that the prefix R(0) . . . R(n) is in L. By a result of Agafonoff [1], a sequence is normal if and only if any subsequence selected by a regular language is again normal. Kamae and Weiss [11] and others have raised the question of how complex a language must be such that selecting according to the language does not preserve normality. We show that there are such languages that are only slightly more complicated than regular ones, namely, normality is neither preserved by linear languages nor by deterministic one-counter languages. In fact, for both types of languages it is possible to select a constant sequence from a normal one.

UR - http://www.scopus.com/inward/record.url?scp=33746355179&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33746355179&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-45138-9_54

DO - 10.1007/978-3-540-45138-9_54

M3 - Chapter

AN - SCOPUS:33746355179

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 602

EP - 611

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Rovan, Branislav

A2 - Vojtas, Peter

PB - Springer Verlag

ER -

Merkle W, Reimann J. On selection functions that do not preserve normality. In Rovan B, Vojtas P, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 602-611. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-45138-9_54

On selection functions that do not preserve normality

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this