{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T18:52:40Z","timestamp":1784227960925,"version":"3.55.0"},"reference-count":33,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T00:00:00Z","timestamp":1702857600000},"content-version":"vor","delay-in-days":351,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"anr","award":["ANR-18-CE40-0007"],"award-info":[{"award-number":["ANR-18-CE40-0007"]}]},{"name":"anr","award":["ANR-22-CE40-0011"],"award-info":[{"award-number":["ANR-22-CE40-0011"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2023,8,3]]},"published-print":{"date-parts":[[2023]]},"abstract":"<jats:p>Using the classic two\u2019s 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\u2019s 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\u2019s complement notation as an increasing bijection between \u2124 and a particular language.<\/jats:p>","DOI":"10.1051\/ita\/2023007","type":"journal-article","created":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T09:05:29Z","timestamp":1702890329000},"page":"12","source":"Crossref","is-referenced-by-count":2,"title":["A Fibonacci analogue of the two\u2019s complement numeration system"],"prefix":"10.1051","volume":"57","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7330-2718","authenticated-orcid":false,"given":"S\u00e9bastien","family":"Labb\u00e9","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jana","family":"Lep\u0161ov\u00e1","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"250","published-online":{"date-parts":[[2023,12,18]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1080\/00150517.2013.12427944","volume":"51","author":"Ahlbach","year":"2013","journal-title":"Fibonacci Quart."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Berstel J., Fibonacci words \u2013 a survey, in The Book of L. (1986) 13\u201327.","DOI":"10.1007\/978-3-642-95486-3_2"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Berth\u00e9 V. and Rigo M. (Eds.), Combinatorics, Automata and Number Theory, Vol. 135 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2010).","DOI":"10.1017\/CBO9780511777653"},{"key":"R4","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1080\/00150517.1992.12429361","volume":"30","author":"Bunder","year":"1992","journal-title":"Fibonacci Quart."},{"key":"R5","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1080\/00150517.1968.12431213","volume":"6","author":"Carlitz","year":"1968","journal-title":"Fibonacci Quart."},{"key":"R6","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1112\/jlms\/s1-35.2.143","volume":"35","author":"Daykin","year":"1960","journal-title":"J. London Math. Soc."},{"key":"R7","unstructured":"Dickson L.E., History of the Theory of Numbers. Vol. I of Divisibility and primality. Chelsea Publishing Co., New York (1966)."},{"key":"R8","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1080\/00029890.1985.11971550","volume":"92","author":"Fraenkel","year":"1985","journal-title":"Amer. Math. Monthly"},{"key":"R9","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0890-5401(88)90050-8","volume":"77","author":"Frougny","year":"1988","journal-title":"Inform. Comput."},{"key":"R10","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1109\/18.75263","volume":"37","author":"Frougny","year":"1991","journal-title":"IEEE Trans. Inform. Theory"},{"key":"R11","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1051\/ita:1999107","volume":"33","author":"Frougny","year":"1999","journal-title":"Theor. Inform. Appl."},{"key":"R12","unstructured":"Frougny C. and Solomyak B., On representation of integers in linear numeration systems, in Ergodic Theory of ZdActions (Warwick, 1993\u20131994), Vol. 228 of London Math. Soc. Lecture Note Ser. Cambridge University Press, Cambridge (1996) 345\u2013368."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Frougny C. and Sakarovitch J., Number representation and finite automata, in Combinatorics, Automata and Number Theory, Vol. 135 of Encyclopedia Math. Appl. Cambridge University Press, Cambridge (2010) 34\u2013107.","DOI":"10.1017\/CBO9780511777653.003"},{"key":"R14","unstructured":"Graham R.L., Knuth D.E. and Patashnik O., Concrete mathematics, 2nd edn. Addison-Wesley Publishing Company, Reading, MA (1994)."},{"key":"R15","unstructured":"Hoggatt V.E.J., Fibonacci and Lucas Numbers. Houghton Mifflin Company IV, Boston (1969) 92."},{"key":"R16","unstructured":"Knuth D.E., The art of Computer Programming, Vol. 1. Addison-Wesley, Reading, MA (1997)."},{"key":"R17","unstructured":"Knuth D.E., The Art of Computer Programming. Vol. 2. Addison-Wesley, Reading, MA (1998)."},{"key":"R18","unstructured":"Knuth D.E., The art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ (2011)."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Labb\u00e9 S. and Lep\u0161ov\u00e1 J., A numeration system for Fibonacci-like Wang shifts, in Combinatorics on Words, Vol. 12847 of Lecture Notes in Comput. Sci. Springer, Cham (2021) 104\u2013116.","DOI":"10.1007\/978-3-030-85088-3_9"},{"key":"R20","unstructured":"Labb\u00e9 S. and Lep\u0161ov\u00e1 J., Dumont\u2013Thomas Numeration Systems for \u2124. (2023) arXiv:2302.14481."},{"key":"R21","first-page":"190","volume":"29","author":"Lekkerkerker","year":"1952","journal-title":"Simon Stevin"},{"key":"R22","unstructured":"Linz P., An Introduction to Formal Languages and Automata, 5th edn. Jones & Bartlett Learning, Sudbury, MA (2012)."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Lothaire M., Algebraic Combinatorics on Words (Cambridge University Press: Cambridge), 2002","DOI":"10.1017\/CBO9781107326019"},{"key":"R24","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.aam.2019.03.003","volume":"108","author":"Massuir","year":"2019","journal-title":"Adv. Appl. Math."},{"key":"R25","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1051\/ita\/2016010","volume":"50","author":"Mousavi","year":"2016","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"R26","unstructured":"OEIS Foundation Inc., Entry A003482 in the on-line encyclopedia of integer sequences (2023)."},{"key":"R27","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF02940581","volume":"1","author":"Ostrowski","year":"1922","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"R28","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF01897025","volume":"15","author":"Parry","year":"1964","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"R29","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/BF02020331","volume":"8","author":"R\u00e9nyi","year":"1957","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"R30","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0890-5401(87)90020-4","volume":"74","author":"Sakarovitch","year":"1987","journal-title":"Inform. and Comput."},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Sakarovitch J., Elements of Automata Theory. Cambridge University Press, Cambridge (2009).","DOI":"10.1017\/CBO9781139195218"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Vorobiev N.N., Fibonacci Numbers. Birkh\u00e4user Verlag, Basel (2002).","DOI":"10.1007\/978-3-0348-8107-4"},{"key":"R33","first-page":"179","volume":"41","author":"Zeckendorf","year":"1972","journal-title":"Bull. Soc. Roy. Sci. Li\u00e8ge"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2023007\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,6]],"date-time":"2024-11-06T06:27:26Z","timestamp":1730874446000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2023007"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"references-count":33,"alternative-id":["ita230002"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2023007","relation":{},"ISSN":["0988-3754","2804-7346"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"2804-7346","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]}}}