Zobrazeno 1 - 10
of 17
pro vyhledávání: '"Benny Porat"'
Publikováno v:
Algorithmica. 81:2857-2875
Data analysis typically involves error recovery and detection of regularities as two different key tasks. In this paper we show that there are data types for which these two tasks can be powerfully combined. A common notion of regularity in strings i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3fea5291c230f0f9385308e609acf4cc
https://doi.org/10.1007/s00453-019-00559-8
https://doi.org/10.1007/s00453-019-00559-8
Publikováno v:
Information and Computation. 214:112-118
We reconsider the well-known problem of pattern matching under the Hamming distance. Previous approaches have shown how to count the number of mismatches efficiently, especially when a bound is known for the maximum Hamming distance. Our interest is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ce8418c7c043dbab5c4f82b5015db41f
https://doi.org/10.1016/j.ic.2012.02.007
https://doi.org/10.1016/j.ic.2012.02.007
Publikováno v:
Theoretical Computer Science. 411(43):3814-3822
There is no known algorithm that solves the general case of the approximate edit distance problem, where the edit operations are insertion, deletion, mismatch, and swap, in time o(nm), where n is the length of the text and m is the length of the patt
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::58a0ca262e96c389a60b2097e621b794
Publikováno v:
Theoretical Computer Science. 407:587-590
In pattern matching with the pair correlation distance problem, the goal is to find all occurrences of a pattern P of length m, in a text T of length n, where the distance between them is less than a threshold k. For each text location i, the distanc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a9bdfd63510adaafd2b8489d7ae2f118
https://doi.org/10.1016/j.tcs.2008.08.023
https://doi.org/10.1016/j.tcs.2008.08.023
Autor:
Amihood Amir, Benny Porat
Publikováno v:
Combinatorial Pattern Matching ISBN: 9783319199283
CPM
CPM
Vertex Relabeling is a variant of the graph relabeling problem. In this problem, the input is a graph and two vertex labelings, and the question is to determine how close are the labelings. The distance measure is the minimum number of label swaps ne
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8d197bb15d315fbacaa1e3696bd839a5
https://doi.org/10.1007/978-3-319-19929-0_1
https://doi.org/10.1007/978-3-319-19929-0_1
Autor:
Amihood Amir, Benny Porat
Publikováno v:
Combinatorial Pattern Matching ISBN: 9783319075655
CPM
CPM
Palindrome recognition is a classic problem in computer science. It is an example of a language that can not be recognized by a deterministic finite automaton and is often brought as an example of a problem whose decision by a single-tape Turing mach
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::585a7bcdd52ba8419a1270498d6598a1
https://doi.org/10.1007/978-3-319-07566-2_3
https://doi.org/10.1007/978-3-319-07566-2_3
Autor:
Amihood Amir, Benny Porat
Publikováno v:
Algorithms and Computation ISBN: 9783642450297
ISAAC
ISAAC
The Sorting by Reversals Problem is known to be \(\cal{NP}\)-hard. A simplification, Sorting by Signed Reversals is polynomially computable. Motivated by the Pattern Matching with Rearrangements model, we consider Pattern Matching with Reversals. Sin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c978c8b1c7f4070edec9dcc8a6c17f63
https://doi.org/10.1007/978-3-642-45030-3_6
https://doi.org/10.1007/978-3-642-45030-3_6
Autor:
Ayelet Butman, Benny Porat, Peter Clifford, Benjamin Sach, Raphaël Clifford, Ely Porat, Markus Jalsenius, Noa Lewenstein
Publikováno v:
Butman, A, Peter, C, Clifford, R, Jalsenius, M T, Lewenstein, N, Porat, B & Porat, E 2013, ' Pattern matching under polynomial transformation ', SIAM Journal on Computing, vol. 42, no. 2, pp. 611-633 . https://doi.org/10.1137/110853327
We consider a class of pattern matching problems where a normalising transformation is applied at every alignment. Normalised pattern matching plays a key role in fields as diverse as image processing and musical information processing where applicat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::14a560671d01392fe5c519cc1a9ee65c
Autor:
Ely Porat, Benny Porat
Publikováno v:
FOCS
We present a fully online randomized algorithm for the classical pattern matching problem that uses merely O(log m) space, breaking the O(m) barrier that held for this problem for a long time. Our method can be used as a tool in many practical applic
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8de4c816a35e9b1665b11a4060ea0ecd
https://doi.org/10.1109/focs.2009.11
https://doi.org/10.1109/focs.2009.11
Publikováno v:
Combinatorial Pattern Matching ISBN: 9783540690665
CPM
CPM
We present a deterministic black box solution for online approximate matching. Given a pattern of length mand a streaming text of length nthat arrives one character at a time, the task is to report the distance between the pattern and a sliding windo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::dd8595133dd59945dc65e816d9318dc5
https://doi.org/10.1007/978-3-540-69068-9_15
https://doi.org/10.1007/978-3-540-69068-9_15