Directed Acyclic Subsequence Graph - overview

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F03%3A03089712" target="_blank" >RIV/68407700:21230/03:03089712 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Directed Acyclic Subsequence Graph - overview

Popis výsledku v původním jazyce

The subsequence matching problem is to decide, for given strings S and T, whether S is a subsequence of T. The string S is called the pattern and the string T the text. We consider the case of multiple texts and show how to solve the subsequence matchingproblem in time linear in the length of the pattern. For this purpose we build an automaton that accepts all subsequences of given texts. We prove an upper bound for its number of states. Furthermore, we consider a modification of the subsequence matching problem: given a string S and a finite language L, we are to decide whether S is a subsequence of any string in L.

Název v anglickém jazyce

Directed Acyclic Subsequence Graph - overview

Popis výsledku anglicky

The subsequence matching problem is to decide, for given strings S and T, whether S is a subsequence of T. The string S is called the pattern and the string T the text. We consider the case of multiple texts and show how to solve the subsequence matchingproblem in time linear in the length of the pattern. For this purpose we build an automaton that accepts all subsequences of given texts. We prove an upper bound for its number of states. Furthermore, we consider a modification of the subsequence matching problem: given a string S and a finite language L, we are to decide whether S is a subsequence of any string in L.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

JD - Využití počítačů, robotika a její aplikace

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F01%2F1433" target="_blank" >GA201/01/1433: Vyhledávání v textu</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2003

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Discrete Algorithms

ISSN

1570-8667

e-ISSN

—

Svazek periodika

1

Číslo periodika v rámci svazku

3-4

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

26

Strana od-do

255-280

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—