Artur Jez

Anthony W. Lin

Proc. ACM Program. Lang., January, 2024

Space-Efficient Conversions from SLPs.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2024: Theoretical Informatics, 2024

2023

Decision Procedures for Sequence Theories (Technical Report).

[BibT_eX]

[DOI]

CoRR, 2023

Decision Procedures for Sequence Theories.

[BibT_eX]

[DOI]

Proceedings of the Computer Aided Verification - 35th International Conference, 2023

2022

Word equations in non-deterministic linear space.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2022

Space-efficient conversions from SLPs.

[BibT_eX]

[DOI]

Travis Gagie

Gonzalo Navarro

CoRR, 2022

Data Path Queries over Embedded Graph Databases.

[BibT_eX]

[DOI]

Diego Figueira

Anthony W. Lin

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

2021

The Smallest Grammar Problem Revisited.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

Balancing Straight-line Programs.

[BibT_eX]

[DOI]

Moses Ganardi

J. ACM, 2021

Solving One Variable Word Equations in the Free Group in Cubic Time.

[BibT_eX]

[DOI]

Robert Ferens

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

2020

Recompression: Technique for Word Equations and Compressed Data.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2020

Solving Word Equations (And Other Unification Problems) by Recompression (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020

2019

Deciding Context Unification.

[BibT_eX]

[DOI]

J. ACM, 2019

Deciding Context Unification (with Regular Constraints).

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 23rd International Conference, 2019

2018

On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2018

Sliding Windows over Context-Free Languages.

[BibT_eX]

[DOI]

Moses Ganardi

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Edit Distance with Block Operations.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Unambiguous conjunctive grammars over a one-symbol alphabet.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Constructing small tree grammars and small circuits for formulas.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

Word equations in linear space.

[BibT_eX]

[DOI]

CoRR, 2017

Approximation ratio of RePair.

[BibT_eX]

[DOI]

Danny Hucke

CoRR, 2017

Recompression: New Approach to Word Equations and Context Unification (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Word Equations in Nondeterministic Linear Space.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Improvements on Re-Pair Grammar Compressor.

[BibT_eX]

[DOI]

Michal Ganczorz

Proceedings of the 2017 Data Compression Conference, 2017

Recompression of SLPs.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

2016

Least and greatest solutions of equations over sets of integers.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

A really simple approximation of smallest grammar.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Equations over sets of integers with addition only.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2016

Recompression: A Simple and Powerful Technique for Word Equations.

[BibT_eX]

[DOI]

J. ACM, 2016

Approximation of smallest linear tree grammar.

[BibT_eX]

[DOI]

Inf. Comput., 2016

Finding all solutions of equations in free groups and monoids with involution.

[BibT_eX]

[DOI]

Volker Diekert

Wojciech Plandowski

Inf. Comput., 2016

One-Variable Word Equations in Linear Time.

[BibT_eX]

[DOI]

Algorithmica, 2016

Solutions of Word Equations Over Partially Commutative Structures.

[BibT_eX]

[DOI]

Volker Diekert

Manfred Kufleitner

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

LZ77 Factorisation of Trees.

[BibT_eX]

[DOI]

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

2015

Approximation of grammar-based compression via recompression.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Faster Fully Compressed Pattern Matching by Recompression.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2015

2014

The Complexity of Compressed Membership Problems for Finite Automata.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2014

Validating the Knuth-Morris-Pratt Failure Function, Fast and Online.

[BibT_eX]

[DOI]

Lukasz Jez

Theory Comput. Syst., 2014

Computational completeness of equations over sets of natural numbers.

[BibT_eX]

[DOI]

Inf. Comput., 2014

Context Unification is in PSPACE.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

A <i>ϕ</i>-competitive algorithm for collecting items with increasing weights from a dynamic queue.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Hyper-Minimization for Deterministic Tree Automata.

[BibT_eX]

[DOI]

Andreas Maletti

Int. J. Found. Comput. Sci., 2013

Collecting Weighted Items from a Dynamic Queue.

[BibT_eX]

[DOI]

Algorithmica, 2013

Unambiguous Conjunctive Grammars over a One-Letter Alphabet.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 17th International Conference, 2013

Recompression: Word Equations and Beyond.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 17th International Conference, 2013

2012

Representing Hyper-arithmetical Sets by Equations over Sets of Integers.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2012

Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P).

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

2011

One-Nonterminal Conjunctive Grammars over a Unary Alphabet.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Complexity of Equations over Sets of Natural Numbers.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Length-reducing Automata (almost) without Auxiliary Symbols.

[BibT_eX]

[DOI]

Tomasz Jurdzinski

J. Autom. Lang. Comb., 2011

Computing All ℓ-Cover Automata Fast.

[BibT_eX]

[DOI]

Andreas Maletti

Proceedings of the Implementation and Application of Automata, 2011

On Minimising Automata with Errors.

[BibT_eX]

[DOI]

Andreas Maletti

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

2010

Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Univariate Equations Over Sets of Natural Numbers.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2010

On Equations over Sets of Integers.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2009

On the two-dimensional cow search problem.

[BibT_eX]

[DOI]

Jakub Lopuszanski

Inf. Process. Lett., 2009

Optimal, online validation of the pi and pi' failure functions

[BibT_eX]

[DOI]

Lukasz Jez

CoRR, 2009

Equations over Sets of Natural Numbers with Addition Only.

[BibT_eX]

[DOI]

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Hyper-minimisation Made Efficient.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

2008

Conjunctive Grammars Generate Non-Regular Unary Languages.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2008

Graphical complexity of products of permutation groups.

[BibT_eX]

[DOI]

Mariusz Grech

Andrzej Kisielewicz

Discret. Math., 2008

Generalized Whac-a-Mole

[BibT_eX]

[DOI]

CoRR, 2008

Complexity of solutions of equations over sets of natural numbers.

[BibT_eX]

[DOI]

Proceedings of the STACS 2008, 2008

2007

Conjunctive Grammars Can Generate Non-regular Unary Languages.

[BibT_eX]

[DOI]