Finite automata for testing composition-based reconstructibility of sequences
From MaRDI portal
Abstract: We investigate the condition under which the Eulerian trail of a digraph is unique, and design a finite automaton to examine it. The algorithm is effective, for if the condition is violated, it will be noticed immediately without the need to trace through the whole trail.
Recommendations
- scientific article; zbMATH DE number 1156634
- Word assembly through minimal forbidden words
- Reconstructing words from subwords in linear time
- Reconstruction of sequences
- Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. I. Reconstruction without forbidden words
Cites work
- scientific article; zbMATH DE number 3478914 (Why is no real title available?)
- scientific article; zbMATH DE number 1024080 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- Approximate string-matching with q-grams and maximal matches
- DNA physical mapping and alternating Eulerian cycles in colored graphs
- Eulerian graphs and related topics. Part 1, Volume 1
- Grammatical Complexity and One-Dimensional Dynamical Systems
- Phase transition in sequence unique reconstruction
- Shuffling biological sequences
- Uniquely decodable n-gram embeddings
Cited in
(5)- A case study in meta-automation: automatic generation of congruence automata for combinatorial sequences
- Self-matched Patterns, Golomb Rulers, and Sequence Reconstruction
- scientific article; zbMATH DE number 5630707 (Why is no real title available?)
- Reconstruction of sequences
- Deciding unique decodability of bigram counts via finite automata
This page was built for publication: Finite automata for testing composition-based reconstructibility of sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q931728)
