2026-09-08T01:21:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26548 2026-09-05T19:47:15Z ddc:004 open_access

Gray Codes with Constant Delay and Constant Auxiliary Space Amarilli, Antoine David, Claire Francis, Nadime Marsault, Victor Monet, Mikaël Strozecki, Yann Gray code Constant delay Constant auxiliary space Enumeration algorithms Linear bounded automata Tape machine Deque machines Counter implementation We give the first two algorithms to enumerate all binary words of {0,1}^𝓁 (like Gray codes) while ensuring that the delay and the auxiliary space is independent from 𝓁, i.e., constant time for each word, and constant memory in addition to the 𝓁 bits storing the current word. Our algorithms are given in two new computational models: tape machines and deque machines. We also study more restricted models, queue machines and stack machines, and show that they cannot enumerate all binary words with constant auxiliary space, even with unrestricted delay. A tape machine is a Turing machine that stores the current binary word on a single working tape of length 𝓁 (which never increases), using no other tape. The machine has a single head and must edit its tape to reach all possible words of {0,1}^𝓁, and output them (in unit time, by entering special output states), with no duplicates. Hence a tape machine uses constant auxiliary space by definition (up to the head position). We construct a tape machine that achieves this task with constant delay between consecutive outputs, so that the machine implements a so-called skew-tolerant quasi-Gray code. We then construct a more involved tape machine that implements a Gray code. A deque machine stores the current binary word on a double-ended queue of length 𝓁, and stores a constant-size internal state. It works as a tape machine, except that it modifies the content of the deque by performing push and pop operations on the endpoints. Hence again a deque machine uses constant auxiliary space by definition. We construct deque machines that enumerate all words of {0,1}^𝓁 with constant-delay. The main technical challenge in this model is to correctly detect when enumeration has finished. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Amarilli and Claire David and Nadime Francis and Victor Marsault and Mikaël Monet and Yann Strozecki 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.160 urn:nbn:de:0030-drops-265485 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.160 eng https://creativecommons.org/licenses/by/4.0/legalcode