Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Computer-Aided Constructions of Commafree Codes

Computer-Aided Constructions of Commafree Codes We determine the maximum size Wk(n)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_k(n)$$\end{document} of a commafree code with codeword length k and alphabet size n for a few previously unknown values of k and n. With the aid of modern SAT solver tooling we prove that W4(5)=139\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_4(5) = 139$$\end{document}, W6(3)=113\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_6(3) = 113$$\end{document}, and W12(2)=334\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_{12}(2) = 334$$\end{document} and exhibit codes that achieve these bounds. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Automated Reasoning Springer Journals

Computer-Aided Constructions of Commafree Codes

Windsor, Aaron A.
Journal of Automated Reasoning , Volume 67 (1) – Mar 1, 2023
Download PDF
10 pages

Loading next page...
 
/lp/springer-journals/computer-aided-constructions-of-commafree-codes-lJBDFied3Y
Publisher
Springer Journals
Copyright
Copyright © The Author(s), under exclusive licence to Springer Nature B.V. 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
ISSN
0168-7433
eISSN
1573-0670
DOI
10.1007/s10817-023-09662-6
Publisher site
See Article on Publisher Site

Abstract

We determine the maximum size Wk(n)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_k(n)$$\end{document} of a commafree code with codeword length k and alphabet size n for a few previously unknown values of k and n. With the aid of modern SAT solver tooling we prove that W4(5)=139\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_4(5) = 139$$\end{document}, W6(3)=113\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_6(3) = 113$$\end{document}, and W12(2)=334\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$W_{12}(2) = 334$$\end{document} and exhibit codes that achieve these bounds.

Journal

Journal of Automated Reasoning – Springer Journals

Published: Mar 1, 2023

Keywords: Commafree codes; Coding theory; SAT Solver; Bounded variable addition

References

  • A computing procedure for quantification theory
    Davis, M; Putnam, H
  • On the construction of comma-free codes
    Eastman, W
  • Comma-free codes
    Golomb, SW; Gordon, B; Welch, LR
  • Cube and conquer: guiding CDCL SAT solvers by lookaheads
    Heule, MJH; Kullmann, O; Wieringa, S; Biere, A; Eder, K; Lourenço, J; Shehory, O
  • Solving and verifying the boolean pythagorean triples problem via cube-and-conquer
    Heule, MJH; Kullmann, O; Marek, VW; Creignou, N; Le Berre, D
  • Recent results in comma-free codes
    Jiggs, BH
  • Computer-aided proof of Erdős discrepancy properties
    Konev, B; Lisitsa, A
  • The van der Waerden number W(2,6)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W(2,6)$$\end{document} is 1132
    Kouril, M; Paul, JL
  • Automated reencoding of boolean formulas
    Manthey, N; Heule, MJH; Biere, A; Biere, A; Nahir, A; Vos, T
  • On maximal comma-free codes (corresp.)
    Niho, Y
  • Translating pseudo-boolean constraints into SAT
    Niklas, E; Sörensson, N
  • Computing binary combinatorial gray codes via exhaustive search with sat solvers
    Zinovik, I; Kroening, D; Chebiryak, Y