Tight lower bounds on the length of word chains

DOI10.1016/0020-0190(90)90136-LzbMath0702.68062OpenAlexW2041883544MaRDI QIDQ915454

Ingo Althöfer

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90136-l

zbMATH Keywords

addition chainde Bruijn-sequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Special sequences and polynomials (11B83)

Related Items (6)

Constructing small tree grammars and small circuits for formulas ⋮ Two-way machines and de Bruijn words ⋮ Finite state complexity ⋮ Deterministic Pushdown Automata and Unary Languages ⋮ DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES ⋮ Simulating finite automata with context-free grammars.

Cites Work

• Unnamed Item
• On the length of word chains
• A note on word chains and regular languages
• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms

This page was built for publication: Tight lower bounds on the length of word chains