Zobrazeno 1 - 10
of 2 032
pro vyhledávání: '"Straight-line programs"'
It was recently proved that any Straight-Line Program (SLP) generating a given string can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size. We generalize this proof to a general class of grammars we call Gener
Externí odkaz:
http://arxiv.org/abs/2404.07057
Autor:
Navarro, Gonzalo, Urbina, Cristian
We explore an extension to straight-line programs (SLPs) that outperforms, for some text families, the measure $\delta$ based on substring complexity, a lower bound for most measures and compressors exploiting repetitiveness (which are crucial in are
Externí odkaz:
http://arxiv.org/abs/2402.09232
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
GANARDI, MOSES1 ganardi@mpi-sws.org, JEŻ, ARTUR2 aje@cs.uni.wroc.pl, LOHREY, MARKUS3 lohrey@eti.uni-siegen.de
Publikováno v:
Journal of the ACM. Jul2021, Vol. 68 Issue 4, p1-40. 40p.
It was recently proved that any SLP generating a given string $w$ can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size. We show that this result also holds for RLSLPs, which are SLPs extended with run-length r
Externí odkaz:
http://arxiv.org/abs/2206.13027
Publikováno v:
IEEE Transactions on Software Engineering, 2023
We target the problem of automatically synthesizing proofs of semantic equivalence between two programs made of sequences of statements. We represent programs using abstract syntax trees (AST), where a given set of semantics-preserving rewrite rules
Externí odkaz:
http://arxiv.org/abs/2109.10476
Autor:
Ganardi, Moses
In grammar-based compression a string is represented by a context-free grammar, also called a straight-line program (SLP), that generates only that string. We refine a recent balancing result stating that one can transform an SLP of size $g$ in linea
Externí odkaz:
http://arxiv.org/abs/2107.00446
Publikováno v:
In Expert Systems With Applications 15 May 2022 194
It is shown that a context-free grammar of size $m$ that produces a single string $w$ (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar for $w$ of size $\mathcal{O}(m)$, whose
Externí odkaz:
http://arxiv.org/abs/1902.03568
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.