Algorithms on Indeterminate Strings

Kód výsledku v IS VaVaI

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

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Algorithms on Indeterminate Strings

Popis výsledku v původním jazyce

A recent paper describes an average-case linear-time algorithm for the calculation of all the borders of every prefix of a string x, where x can contain ''don't-care'' letters that match with any letter of the alphabet. In this paper we show that in facttwo distinct cases arise for the border calculation - we call them ''quantum'' and ''deterministic'', and both of them can arise in practice. The existing algorithm applies to the quantum case, but we show how to modify it to deal with the deterministiccase. We then extend the border algorithms to apply also to what we call ''indeterminate strings''. We also discuss other algorithms on these indeterminate strings, some of them left as open problems.

Název v anglickém jazyce

Algorithms on Indeterminate Strings

Popis výsledku anglicky

A recent paper describes an average-case linear-time algorithm for the calculation of all the borders of every prefix of a string x, where x can contain ''don't-care'' letters that match with any letter of the alphabet. In this paper we show that in facttwo distinct cases arise for the border calculation - we call them ''quantum'' and ''deterministic'', and both of them can arise in practice. The existing algorithm applies to the quantum case, but we show how to modify it to deal with the deterministiccase. We then extend the border algorithms to apply also to what we call ''indeterminate strings''. We also discuss other algorithms on these indeterminate strings, some of them left as open problems.

Druh

D - Stať ve sborníku

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

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 statě ve sborníku

Proceedings of the 14th Australian Workshop on Combinatorial Algorithms AWOCA'03

ISBN

89-7282-326-0

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

36-45

Název nakladatele

Seoul National University

Místo vydání

Seoul

Místo konání akce

Seoul

Datum konání akce

13. 7. 2003

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—