Zobrazeno 1 - 10
of 40
pro vyhledávání: '"Danny Hucke"'
Autor:
Danny Hucke, Carl Philipp Reh
Publikováno v:
Algorithms, Vol 14, Iss 2, p 65 (2021)
A grammar-based compressor is an algorithm that receives a word and outputs a context-free grammar that only produces this word. The approximation ratio for a single input word is the size of the grammar produced for this word divided by the size of
Externí odkaz:
https://doaj.org/article/4008000827fd4605befdf45daf149383
Publikováno v:
Theory of Computing Systems. 65:1-18
In the sliding window streaming model the goal is to compute an output value that only depends on the lastnsymbols from the data stream. Thereby, only space sublinear in the window sizenshould be used. Quite often randomization is used in order to ac
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4871720cedd1c06d6db7829e8f276594
https://doi.org/10.1007/s00224-020-10000-1
https://doi.org/10.1007/s00224-020-10000-1
Publikováno v:
IEEE Transactions on Information Theory. 65:6399-6413
The problem of universal source coding for binary trees is considered. Zhang, Yang, and Kieffer derived upper bounds on the average-case redundancy of codes based on directed acyclic graph (DAG) compression for binary tree sources with certain proper
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0302a605d5811d950f6a2f4c41bcffe5
https://doi.org/10.1109/tit.2019.2919829
https://doi.org/10.1109/tit.2019.2919829
Autor:
Carl Philipp Reh, Danny Hucke
Publikováno v:
Algorithms
Volume 14
Issue 2
Algorithms, Vol 14, Iss 65, p 65 (2021)
Volume 14
Issue 2
Algorithms, Vol 14, Iss 65, p 65 (2021)
A grammar-based compressor is an algorithm that receives a word and outputs a context-free grammar that only produces this word. The approximation ratio for a single input word is the size of the grammar produced for this word divided by the size of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::84ea3be5df09846fd2973acad39487c5
Publikováno v:
ACM Transactions on Computation Theory. 10:1-30
The computational complexity of the circuit and expression evaluation problem for finite semirings is considered, where semirings are not assumed to have an additive or a multiplicative identity. The following dichotomy is shown: If a finite semiring
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5ace94f5db5850b040ceff1ece98304b
https://doi.org/10.1145/3241375
https://doi.org/10.1145/3241375
Publikováno v:
String Processing and Information Retrieval ISBN: 9783030592110
SPIRE
SPIRE
Whereas for strings, higher-order empirical entropy is the standard entropy measure, several different notions of empirical entropy for trees have been proposed in the past, notably label entropy, degree entropy, conditional versions of the latter tw
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b7ec2c41ff2ab835d5b36531a0eda8db
https://doi.org/10.1007/978-3-030-59212-7_17
https://doi.org/10.1007/978-3-030-59212-7_17
Autor:
Artur Jeż, Danny Hucke, Hideo Bannai, Carl Philipp Reh, Markus Lohrey, Momoko Hirayama, Shunsuke Inenaga
In a seminal paper of Charikar et al. on the smallest grammar problem, the authors derive upper and lower bounds on the approximation ratios for several grammar-based compressors, but in all cases there is a gap between the lower and upper bound. Her
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::465a1382023f1235cd31b4aa0326c1d8
http://arxiv.org/abs/1908.06428
http://arxiv.org/abs/1908.06428
Autor:
Danny Hucke
Publikováno v:
String Processing and Information Retrieval ISBN: 9783030326852
A grammar-based compressor computes for a given input w a context-free grammar that produces only w. So-called global grammar-based compressors (\(\mathsf {RePair}\), \(\mathsf {LongestMatch}\) and \(\mathsf {Greedy}\)) achieve impressive practical c
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::016081bc082f4aee67d2c90b9a4b2fb0
https://doi.org/10.1007/978-3-030-32686-9_1
https://doi.org/10.1007/978-3-030-32686-9_1
Publikováno v:
Computer Science – Theory and Applications ISBN: 9783030199548
CSR
CSR
In the sliding window streaming model the goal is to compute an output value that only depends on the last n symbols from the data stream. Thereby, only space sublinear in the window size n should be used. Quite often randomization is used in order t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0783cc6c42ae2e80fcb72c0f24d78549
https://doi.org/10.1007/978-3-030-19955-5_21
https://doi.org/10.1007/978-3-030-19955-5_21
Publikováno v:
ISIT
The definition of $k^{th}$-order empirical entropy of strings is extended to node labelled binary trees. A suitable binary encoding of tree straight-line programs (that have been used for grammar-based tree compression before) is shown to yield binar
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ed4a01ae06c9fde709a8df31750e18b1