Title: Decimation-invariant sequences and their automaticity
Authors: BarbĂ©, AndrĂ© ×
Skordev, G #
Issue Date: May-2001
Publisher: Elsevier science bv
Series Title: Theoretical computer science vol:259 issue:1-2 pages:379-403
Abstract: This paper deals with one-dimensional bidirectional sequences (a) under bar : Z --> V, V a finite set, such that any p-decimation (\p \ greater than or equal to 2) of the sequence reproduces the sequence (modulo a certain shift). We develop a procedure for solving the underlying decimation-invariance (DI) equations and find that the number of solutions is always finite. Conditions for equivalency among solutions of differently parametrized DI-problems, and for possible periodicity and symmetry of solutions, are derived. It is shown that the set of all possible p-based decimations of a such a DI sequence (the so-called full kernel of the sequence) is finite. This implies finiteness of the kernel for the separate right and left parts of the sequence, and also \p \ -automaticity of these parts. An algorithm is presented that constructs the kernel and associated \p \ -automaton of a DI-sequence explicitly. (C) 2001 Elsevier Science B.V. All rights reserved.
ISSN: 0304-3975
Publication status: published
KU Leuven publication type: IT
Appears in Collections:ESAT - STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science