Hypercubes and isometric words based on swap and mismatch distance
From MaRDI portal
Publication:6175084
Abstract: The hypercube of dimension n is the graph whose vertices are the 2^n binary words of length n, and there is an edge between two of them if they have Hamming distance 1. We consider an edit distance based on swaps and mismatches, to which we refer as tilde-distance, and define the tilde-hypercube with edges linking words at tilde-distance 1. Then, we introduce and study some isometric subgraphs of the tilde-hypercube obtained by using special words called tilde-isometric words. The subgraphs keep only the vertices that avoid a given tilde-isometric word as a factor. In the case of word 11, the subgraph is called tilde-Fibonacci cube, as a generalization of the classical Fibonacci cube. The tilde-hypercube and the tilde-Fibonacci cube can be recursively defined; the same holds for the number of their edges. This allows an asymptotic estimation of the number of edges in the tilde-Fibonacci cube, in comparison to the total number in the tilde-hypercube.
Recommendations
Cites work
- A characterization of non-isometric binary words
- A survey of the theory of hypercube graphs
- Asymptotic number of isometric generalized Fibonacci cubes
- Characterization and measure of infinite two-dimensional strong prefix codes
- Checking whether a word is Hamming-isometric in linear time
- Circular embeddability of isometric words
- Generalized Fibonacci cubes
- scientific article; zbMATH DE number 3557227 (Why is no real title available?)
- scientific article; zbMATH DE number 2024859 (Why is no real title available?)
- Hypercubes and isometric words based on swap and mismatch distance
- On \(k\)-ary \(n\)-cubes and isometric words
- On isomorphism classes of generalized Fibonacci cubes
- Proof of a conjecture on 2-isometric words
- Proofs of two conjectures on generalized Fibonacci cubes
- Quaternary n-cubes and isometric words
- Structural and enumerative properties of the Fibonacci cubes
- Structure of Fibonacci cubes: a survey
- Swap and mismatch edit distance
- The index of a binary word
- The String-to-String Correction Problem
- The structures of bad words
Cited in
(23)- On \(k\)-ary \(n\)-cubes and isometric words
- Quaternary n-cubes and isometric words
- Isometric words based on swap and mismatch distance
- Hypercubes and isometric words based on swap and mismatch distance
- Isometric words and edit distance: main notions and new variations
- Density of k-ary words with 0, 1, 2-error overlaps
- Partial cubes and Fibonacci dimension: insights and perspectives
- Characterization of isometric words based on swap and mismatch distance
- On the Weihrauch degree of the additive Ramsey theorem
- Hilbert's tenth problem for term algebras with a substitution operator
- Complemented subsets and Boolean-valued, partial functions
- Defining long words succinctly in FO and MSO
- On the first-order parts of problems in the Weihrauch degrees
- Algorithmically random series
- Ideal presentations and numberings of some classes of effective quasi-Polish spaces
- Lower bounds on () and other properties of -register machines
- Reifying dynamical algebra: maximal ideals in countable rings, constructively
- Maps for learning indexable classes
- On the necessity of some topological spaces
- Computing the index of non-isometric k-ary words with Hamming and Lee distance
- Isometric sets of words and generalizations of the Fibonacci cubes
- A family of partial cubes with minimal Fibonacci dimension
- Transformations between minimally f-free words
This page was built for publication: Hypercubes and isometric words based on swap and mismatch distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6175084)
