We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers using the Dyck ...
详细信息
We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers using the Dyck language. We also show that our framework can be applied to the rational base numeration systems. (C) 2010 Elsevier Inc. All rights reserved.
We study the properties of the function R-(m)(n) defined as the number of representations of an integer n as a sum of distinct m-Bonacci numbers F-k((m)), given by F-i((m))=2(i - 1), for i is an element of{1, 2, ..., ...
详细信息
We study the properties of the function R-(m)(n) defined as the number of representations of an integer n as a sum of distinct m-Bonacci numbers F-k((m)), given by F-i((m))=2(i - 1), for i is an element of{1, 2, ..., m}, F-k+m((m))= F-k+m - 1((m))+F-k+m - 2((m))+...+F-k((m)), for k >= 1. We give a matrix formula for calculating R-(m)(n) from the greedy expansion of n. We determine the maximum of R-(m)(n) for n with greedy expansion of fixed length k, i.e. for F-k((m))<= n < F-k+1((m)). Unlike the Fibonacci case m = 2, the values of the maxima are not related to the sequence (F-k((m)))(k >= 1). We describe the palindromic structure of the sequence (R-(m)(n))(n is an element of N), which is richer than in the case of Fibonacci numeration system.
Using the classic two's complement notation of signed integers, the fundamental arithmetic operations of addition, subtraction, and multiplication are identical to those for unsigned binary numbers. We introduce a...
详细信息
Using the classic two's complement notation of signed integers, the fundamental arithmetic operations of addition, subtraction, and multiplication are identical to those for unsigned binary numbers. We introduce a Fibonacci-equivalent of the two's complement notation and we show that addition in this numeration system can be performed by a deterministic finite-state transducer. The result is based on the Berstel adder, which performs addition of the usual Fibonacci representations of nonnegative integers and for which we provide a new constructive proof. Moreover, we characterize the Fibonacci-equivalent of the two's complement notation as an increasing bijection between DOUBLE-STRUCK CAPITAL Z and a particular language.
In this paper, we describe representations of integers by linear combinations with integer coefficients of squares of the Fibonacci numbers. Focusing on felicitous linear dependence of the Fibonacci squares, we design...
详细信息
In this paper, we describe representations of integers by linear combinations with integer coefficients of squares of the Fibonacci numbers. Focusing on felicitous linear dependence of the Fibonacci squares, we design a numeration system with the Fibonacci squares for representing every integer uniquely.
In this paper, we study representations of real numbers in the positional numeration system with negative base, as introduced by Ito and Sadahiro. We focus on the set Z(-beta) of numbers whose representation uses only...
详细信息
In this paper, we study representations of real numbers in the positional numeration system with negative base, as introduced by Ito and Sadahiro. We focus on the set Z(-beta) of numbers whose representation uses only non-negative powers of -beta, the so-called (-beta)-integers. We describe the distances between consecutive elements of Z(-beta). In case that this set is non-trivial we associate to beta an infinite word v(-beta) over an (in general infinite) alphabet. The self-similarity of Z(-beta), i.e., the property - beta Z(-beta) subset of Z(-beta), allows us to find a morphism under which v(-beta) is invariant. On the example of two cubic irrational bases beta we demonstrate the difference between Rauzy fractals generated by (-beta)-integers and by beta-integers.
Generalizations of numeration systems in which IN is recognizable by a finite automaton are obtained by describing a lexicographically ordered infinite regular language L C Sigma (*). For these systems, we obtain a ch...
详细信息
Generalizations of numeration systems in which IN is recognizable by a finite automaton are obtained by describing a lexicographically ordered infinite regular language L C Sigma (*). For these systems, we obtain a characterization of recognizable sets of integers in terms of N-rational formal series. After a study of the polynomial regular languages, we show that, if the complexity of L is Theta (n(l)) (resp. if L is the complement of a polynomial language), then multiplication by lambda is an element of N preserves recognizability only if lambda = beta (l+1) (resp. if lambda not equal (#Sigma)(beta)) for some beta is an element of N. Finally, we obtain sufficient conditions for the notions of recognizability for abstract systems and some positional number systems to be equivalent. (C) 2001 Elsevier Science B.V. All rights reserved.
Let L be an infinite regular language on a totally ordered alphabet (Sigma, <). Feeding a finite deterministic automaton (with output) with the words of L, enumerated lexicographically with respect to <, leads t...
详细信息
Let L be an infinite regular language on a totally ordered alphabet (Sigma, <). Feeding a finite deterministic automaton (with output) with the words of L, enumerated lexicographically with respect to <, leads to an infinite sequence over the output alphabet of the automaton. This process generalizes the concept of k-automatic sequence for abstract numeration systems on a regular language (instead of systems in base k). Here, we study the first properties of these sequences and their relations with numeration systems. (C) 2000 Elsevier Science B.V. All rights reserved.
Using a genealogically ordered infinite regular language, we know how to represent an interval of R. Numbers having an ultimately periodic representation play a special role in classical numeration systems. The aim of...
详细信息
Using a genealogically ordered infinite regular language, we know how to represent an interval of R. Numbers having an ultimately periodic representation play a special role in classical numeration systems. The aim of this paper is to characterize the numbers having an ultimately periodic representation in generalized systems built on a regular language. The syntactical properties of these words are also investigated. Finally, we show the equivalence of the classical theta-expansions with our generalized representations in some special case related to a Pisot number theta. (C) 2004 Elsevier Inc. All rights reserved.
Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers beta and gamma respectively, such that beta and gamma are multiplicatively dependent, are considered. ...
详细信息
Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers beta and gamma respectively, such that beta and gamma are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number.
Parallel addition in integer base is used for speeding up multiplication and division algorithms, k-block parallel addition has been introduced by Kornerup in [14]: instead of manipulating single digits, one works wit...
详细信息
Parallel addition in integer base is used for speeding up multiplication and division algorithms, k-block parallel addition has been introduced by Kornerup in [14]: instead of manipulating single digits, one works with blocks of fixed length k. The aim of this paper is to investigate how such notion influences the relationship between the base and the cardinality of the alphabet allowing block parallel addition. In this paper, we mainly focus on a certain class of real bases the so-called Parry numbers. We give lower bounds on the cardinality of alphabets of non-negative integer digits allowing block parallel addition. By considering quadratic Pisot bases, we are able to show that these bounds cannot be improved in general and we give explicit parallel algorithms for addition in these cases. We also consider the d-bonacci base, which satisfies the equation X-d = Xd-1 + Xd-2 + ... + X + 1. If in a base being a d-bonacci number I-block parallel addition is possible on an alphabet A, then #A >= d + 1;on the other hand, there exists a k is an element of N such that k-block parallel addition in this base is possible on the alphabet {0, 1, 2}, which cannot be reduced. In particular, addition in the Tribonacci base is 14-block parallel on alphabet {0, 1, 2}. (C) 2014 Elsevier B.V. All rights reserved.
暂无评论