Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-26T00:24:43.486Z Has data issue: false hasContentIssue false
  • English
  • Français

The role of the principal part in factorizing block maps

Published online by Cambridge University Press:  24 October 2008

Frank Rhodes
Frank Rhodes
Affiliation:
Mathematics Department, University of Southampton
Get access Rights & Permissions [Opens in a new window]

Extract

An n-block is a sequence b1 … bn where bi ε {0,1} for 1 ≤ i ≤ n, and an n-block map is a function from the set of n-blocks to the set {0,1}. Block maps can be used to study endomorphisms of the shift dynamical system [7] and shift register sequences [4]. Composition of endomorphisms and cascading of shift registers [6] can be studied via composition of block maps. If fog is a given block map which is linear in the first variable and if g is also given, then f is unique and can be determined. If fog and f are given then g is unique and can be determined, at least up to a constant [10]. However, little is known about the level of computational complexity of the general task of searching for factors of a given block map. In this paper I identify a substantial class of maps which are linear in the first variable but not linear, for which there are effective methods of searching for factors. The methods are based on the presentation of block maps via successive principal parts, introduced in [9]. There I define the principal vector of a block map. One of the key results gives conditions under which there is a particularly close relationship between the principal vectors of two block maps f and g and their composition fog. In the second section of this paper I show that the same relationship holds under weaker conditions.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 96 , Issue 2 , September 1984 , pp. 223 - 235
Copyright
Copyright © Cambridge Philosophical Society 1984

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Coven, E. M., Hedlund, G. A. and Rhodes, F.. The commuting block maps problem. Trans. Amer. Math. Soc. 24 (1979), 113–138.Google Scholar
[2] Davio, M. and Bioul, G.. Taylor-expansion computation from cube arrays. Philips Res. Reports 29 (1974), 401–411.Google Scholar
[3] Ferguson, J. D.. Some properties of Mappings on sequences spaces. Ph.D. dissertation, Yale University, New Haven, 1967.Google Scholar
[4]Golomb, S. W.. Shift Register Sequences (Holden-Day, 1966).Google Scholar
[5] Gbeen, D. H. and Dimond, K. R.. Polynomial representation of nonlinear feedback shiftregisters. Proc. Iee 117 (1970), 56–60.Google Scholar
[6] Gbeen, D. H. and Kelsch, R. G.. Some polynomial compositions of nonlinear feedback shift registers and their sequence-domain consequences. Proc. IEE 117 (1970), 1750–1756.Google Scholar
[7] Hedlund, G. A.. Endomorphisms and automorphisms of the shift dynamical system. Math. Systems Theory 3 (1969), 320–375.Google Scholar
[8] Rhodes, F.. The sums of powers theorem for commuting block maps. Trans. Amer. Math. Soc. 271 (1982), 225–236.CrossRefGoogle Scholar
[9] Rhodes, F.. The principal part of a block map. J. Combin. Theor. Ser. A 33 (1982), 48–64.Google Scholar
[10] Rhodes, F.. Left cancellation of block maps. Bull. London Math. Soc. 16 (1984), 19–24.Google Scholar