About: Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance Goto Sponge Distinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	Jádro je druhem pravidelnosti textových řetězců. Vlastní přibližné jádro w řetězce T je jeho faktor w takový, že w pokrývá nějaký nadřetězec T. V tomto článku je řešen problém vyhledávání všech vlastních přibližných jader řetězce a jejich skutečných vzdáleností a dále je ukázán algoritmus polynomiální v čase i paměti. Vyhledávání je přibližné a je uvažována zadaná maximální Hammingova vzdálenost. Řešení je založeno na teorii konečných (sufixových) automatů, která umožňuje přímočarý návrh stringologických algoritmů. Je tak ukázáno, že množina problémů řešitelných s pomocí konečných automatů obsahuje i vyhledávání přibližných jader. (cs) Seed is a type of a regularity of strings. A restricted approximate seed w of string T is a factor of T such that w covers a superstring of T under some distance rule. In this paper, the problem of all restricted seeds with the smallest Hamming distance is studied and a polynomial time and space algorithm for solving the problem is presented. It searches for all restricted approximate seeds of a string with given limited approximation using Hamming distance and it computes the smallest distance for each found seed. The solution is based on a finite (suffix) automata approach that provides a straightforward way to design algorithms to many problems in stringology. Therefore, it is shown that the set of problems solvable using finite automata includes the one studied in this paper. Seed is a type of a regularity of strings. A restricted approximate seed w of string T is a factor of T such that w covers a superstring of T under some distance rule. In this paper, the problem of all restricted seeds with the smallest Hamming distance is studied and a polynomial time and space algorithm for solving the problem is presented. It searches for all restricted approximate seeds of a string with given limited approximation using Hamming distance and it computes the smallest distance for each found seed. The solution is based on a finite (suffix) automata approach that provides a straightforward way to design algorithms to many problems in stringology. Therefore, it is shown that the set of problems solvable using finite automata includes the one studied in this paper. (en)
Title	Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance (en) Využití konečných automatů při vyhledávání všech jader textu s minimální Hammingovou vzdáleností (cs)
skos:prefLabel	Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance (en) Využití konečných automatů při vyhledávání všech jader textu s minimální Hammingovou vzdáleností (cs)
skos:notation	RIV/68407700:21230/09:03156152!RIV09-MSM-21230___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(GA201/06/1039), P(GA201/09/0807), Z(MSM6840770014)
http://linked.open...iv/cisloPeriodika	2
http://linked.open...vai/riv/dodaniDat	2009
http://linked.open...aciTvurceVysledku	Melichar, Bořivoj Guth, Ondřej
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	České vysoké učení technické v Praze / Fakulta elektrotechnická
http://linked.open...dnocenehoVysledku	315079
http://linked.open...ai/riv/idVysledku	RIV/68407700:21230/09:03156152
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	approximate seed; suffix automaton; Hamming distance; stringology (en)
http://linked.open.../riv/klicoveSlovo	approximate seed suffix automaton stringology Hamming distance
http://linked.open...odStatuVydavatele	HK - Zvláštní administrativní oblast Čínské lidové republiky Hongkong
http://linked.open...ontrolniKodProRIV	[E4BB74D60D94]
http://linked.open...i/riv/nazevZdroje	International Journal of Computer Science
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	String and tree analysis and processing Text processing and analysis
http://linked.open...UplatneniVysledku	2009
http://linked.open...v/svazekPeriodika	36
http://linked.open...iv/tvurceVysledku	Melichar, Bořivoj Guth, Ondřej
http://linked.open...n/vavai/riv/zamer	Výzkum perspektivních informačních a komunikačních technologií
issn	1819-9224
number of pages	10 (xsd:int)
http://localhost/t...ganizacniJednotka	21230
is http://linked.open...avai/riv/vysledek of	Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 85 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software