About: Searching All Approximate Covers and Their Distance using Finite Automata

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

About: Searching All Approximate Covers and Their Distance using Finite Automata Goto Sponge NotDistinct 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	Pokrytí je druhem pravidelnosti textových řetězců. Vlastní přibližné pokrytí w řetězce T je jeho faktor w takový, že se každá pozice řetězce T nachází v nějakém přibližném výskytu faktoru w v řetězci T. V tomto článku je řešen problém vyhledávání všech vlastních přibližných pokrytí ř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 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 pokrytí. (cs) Cover is a type of a regularity of strings. A restricted approximate cover w of string T is a factor of T such that every position of T lies within some approximate occurrence of w in T. In this paper, the problem of all restricted smallest distance approximate covers of a string is studied and a polynomial time and space algorithm for solving the problem is presented. It searches for all restricted approximate covers of a string with given limited approximation using Hamming distance and it computes the smallest distance for each found cover. The solution is based on a finite 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. Cover is a type of a regularity of strings. A restricted approximate cover w of string T is a factor of T such that every position of T lies within some approximate occurrence of w in T. In this paper, the problem of all restricted smallest distance approximate covers of a string is studied and a polynomial time and space algorithm for solving the problem is presented. It searches for all restricted approximate covers of a string with given limited approximation using Hamming distance and it computes the smallest distance for each found cover. The solution is based on a finite 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	Searching All Approximate Covers and Their Distance using Finite Automata Vyhledávání všech přibližných pokrytí textu a jejich vzdáleností s použitím konečných automatů (cs) Searching All Approximate Covers and Their Distance using Finite Automata (en)
skos:prefLabel	Searching All Approximate Covers and Their Distance using Finite Automata Vyhledávání všech přibližných pokrytí textu a jejich vzdáleností s použitím konečných automatů (cs) Searching All Approximate Covers and Their Distance using Finite Automata (en)
skos:notation	RIV/68407700:21230/08:03146046!RIV09-MSM-21230___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(GA201/06/1039), Z(MSM6840770014)
http://linked.open...vai/riv/dodaniDat	2009
http://linked.open...aciTvurceVysledku	Melichar, Bořivoj Guth, Ondřej Balík, Miroslav
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
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	393972
http://linked.open...ai/riv/idVysledku	RIV/68407700:21230/08:03146046
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Hamming distance; cover; finite automaton; string; suffix automaton (en)
http://linked.open.../riv/klicoveSlovo	cover string finite automaton suffix automaton Hamming distance
http://linked.open...ontrolniKodProRIV	[8BC2E95D6456]
http://linked.open...v/mistoKonaniAkce	Hrebinok, Vysoké Tatry
http://linked.open...i/riv/mistoVydani	Košice
http://linked.open...i/riv/nazevZdroje	Information Technologies - Applications and Theory
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Text processing and analysis
http://linked.open...UplatneniVysledku	2008
http://linked.open...iv/tvurceVysledku	Balík, Miroslav Melichar, Bořivoj Guth, Ondřej
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2008-09-22 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Výzkum perspektivních informačních a komunikačních technologií
number of pages	6 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Univerzita P. J. Šafárika
https://schema.org/isbn	978-80-969184-9-2
http://localhost/t...ganizacniJednotka	21230
is http://linked.open...avai/riv/vysledek of	Searching All Approximate Covers and Their Distance using Finite Automata Searching All Approximate Covers and Their Distance using Finite Automata Searching All Approximate Covers and Their Distance using Finite Automata Searching All Approximate Covers and Their Distance using Finite Automata

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, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software