Universal sequences

DOI10.1007/S002000050071MaRDI QIDQ1360981zbMATH OpenOpenAlexFDO

Authors Henk D. L. Hollmann, Jack van Lint

Publication date 24 November 1998

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://research.tue.nl/nl/publications/af2e5a59-d694-412d-8f7a-5e663de34e15

zbMATH Keywords

\((0,1)\)-test sequencescircle sequencessubsequencestest sequence lengthuniversal sequencesVLSI-testing

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Fault detection; testing in circuits and networks (94C12)

Review text

Untersucht wird wie lang mindestens eine \((0,1)\)-Test-Folge sein muß, um darin für jedes \(m\) (mit \(k\leq m\leq n\) bei vorgegebenen \(k,n)\) mit \(2^{k}\) Teilfolgen davon alle \((0,1)\)-Folgen der Länge \(k\) zu erhalten, wobei die Teilfolgen spätestens mit dem jeweils \(m\)-ten Folge-Element der Test-Folge vom Teilfolgen-Beginn an endet. Offensichtlich ist die Test-Folgen-Länge bei \(k=n\) mindestens \(2^{k+ (n-1)}\), bei Kreis-Folgen \(2^k\); es gilt sogar Gleichheit wegen Existenz der DeBruijn-Folgen. Für verschiedene Einschränkungen werden Abschätzungen gegeben, insbesondere für \(m=n\). Mit Hilfe von Euler's varphi-Funktion wird auch gezeigt, daß sich Kreis-Testfolgen für \(n\) = Primzahl leicht daraus ableiten lassen.

Recommendations

• Universal Traversal Sequences
• Universal sequences of functions
• Bounds on Universal Sequences
• scientific article; zbMATH DE number 2145366
• scientific article; zbMATH DE number 575916
• Universal prediction of individual sequences
• LATIN 2004: Theoretical Informatics
• scientific article; zbMATH DE number 2174395
• scientific article; zbMATH DE number 3849210

Cited in

(1)

• Jack van Lint (1932--2004): a survey of his scientific work

This page was built for publication: Universal sequences

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