Sequences of binary strings with relation of conditional simplicity

MaRDI QIDQ5960250zbMATH OpenFDO

Authors Andrei Romashchenko

Publication date 14 April 2002

Published in Moscow University Mathematics Bulletin (Search for Journal in Brave)

zbMATH Keywords

analogue of Turing degrees of unsolvabilitysequence of binary strings

Mathematics Subject Classification ID

Semilattices (06A12) Information theory (general) (94A15) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Review text

The author considers a finite analogue of the Turing degrees of unsolvability [\textit{J.~Shenfield}, ``Degrees of unsolvability, Nauka, Moscow (1977)] and determines a partial order formalizing the intuitive relation ``\(x\) is simple with respect to \(y\). It is shown that the partially ordered set defined in this way is an upper semi-lattice, rather than a lattice.

Recommendations

• Binary sequences. I: Complexity
• A note on ternary sequences of strings of 0 and 1
• Binary strings and the Jacobsthal numbers
• On the Compatibility of Binary Sequences
• scientific article; zbMATH DE number 5150220
• Some generalizations on counting binary strings
• On a Class of Binary Sequences
• De Bruijn sequences for fixed-weight binary strings
• A complexity measure for families of binary sequences
• scientific article; zbMATH DE number 1740058

Cited in

(2)

• The degrees of conditional problems
• Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)

This page was built for publication: Sequences of binary strings with relation of conditional simplicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5960250)