Homepage
Artur Jeż
MaxPlanckInstitut für Informatik
Department D1: Algorithms and Complexity
Campus E1 4, Room 320
66123 Saarbrücken
Germany
Email:
Get my email address via email
Phone: +49 681 9325 1020
Fax: +49 681 9325 199
 Word equations
 Algorithms for compressed data
 Finite Automata and algorithms for them
String algorithms (and related)
 A. Jeż
Context unification is in PSPACE
41st International Colloquium on Automata, Languages and Programming (ICALP (B)) 2015
[arXiv, presentation]
 V. Diekert, A. Jeż, W. Plandowski
Finding All Solutions of Equations in Free Groups and Monoids with Involution
9th International Computer Science Symposium in Russia 2015
[arXiv]
 A. Jeż
A really simple approximation of smallest grammar
25th Annual Symposium on Combinatorial Pattern Matching (CPM) 2014
[arXiv, presentation]
 A. Jeż, M. Lohrey
Approximation of smallest linear tree grammar
31st International Symposium on Theoretical Aspects of Computer Science (STACS) 2014
[arXiv, presentation]
 A. Jeż
Onevariable word equations in linear time
40th International Colloquium on Automata, Languages and Programming (ICALP) (track B) 2013
[arXiv, presentation]
 A. Jeż
Recompression: Word Equations and Beyond (invited paper)
17th Internation Conference on Developments in Language Theory (DLT) 2013
[presentation]
 A. Jeż
Approximation of GrammarBased Compression via Recompression
24th Annual Symposium on Combinatorial Pattern Matching (CPM) 2013
[arXiv, presentation]
 A. Jeż
Recompression: a simple and powerful technique for word equations
30th International Symposium on Theoretical Aspects of Computer Science (STACS) 2013
[conference version, arXiv, presentation]
 A. Jeż
Faster fully compressed pattern matching by recompression
39th International Colloquium on Automata, Languages and Programming (ICALP) (track A) 2012
[arXiv, presentation]
 P.
Gawrychowski, A. Jeż, Ł.
Jeż
Validating the KnuthMorrisPratt failure function, fast and online
5th International Computer Science Symposium in Russia (CSR) 2010
full version: Theory of Computing Systems (available online)
[journal, presentation]
Automata
 A. Jeż, A. Maletti
HyperMinimiżation for Deterministic Tree Automata
17th International Conference on Implementation and Application of Automata (CIAA) 2012

A. Jeż
Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)
29th International Symposium on Theoretical Aspects of Computer Science (STACS) 2012
full version: Theory of Computing Systems
[conference, arXiv,
journal]
 A. Jeż, A. Maletti
Computing all lcover automata fast
16th International Conference on Implementation and Application of Automata (CIAA) 2011
[.pdf]
 P.
Gawrychowski, A. Jeż, A. Maletti
On minimising automata with errors
36th International Symposiums on Mathematical Foundations of Computer Science (MFCS) 2011
[arXiv]
 P. Gawrychowski, A. Jeż
Hyperminimisation made efficient
34th International Symposiums on Mathematical Foundations of Computer Science (MFCS) 2009
Best student paper award
[conference
version, rough full version,
presentation]
Systems of Equations over Sets of Numbers
 A. Jeż, A. Okhotin
Unambiguous Conjunctive Grammars over a OneLetter Alphabet
17th Internation Conference on Developments in Language Theory (DLT) 2013
 A. Jeż, A. Okhotin
On the number of nonterminal symbols in unambiguous conjunctive grammars
14th International Workshop on Descriptional Complexity of Formal Systems (DCFS) 2012

A. Jeż, A. Okhotin
Univariate Equations Over Sets of Natural Numbers
Fundamenta informaticae 104, 329348 (2010)
[available on request]
 A. Jeż, A. Okhotin
Least and greatest solutions of equations over sets of integers
35th International Symposiums on Mathematical Foundations of Computer Science (MFCS) 2010
[.ps, .pdf,
presentation]
 A. Jeż, A. Okhotin
On equations over sets of integers
27th International Symposium on Theoretical Aspects of Computer Science (STACS) 2010
full version:
Representing Hyperarithmetical Sets by Equations over Sets of Integers
Theory of Computing Systems, 51:2, 196228 (2012)
[.pdf,
presentation]
 A. Jeż, A. Okhotin
Onenonterminal
conjunctive grammars over a unary alphabet
4th International Computer Science Symposium in Russia (CSR) 2009
full version: Theory of Computing Systems
49:2, 319342 (2011)
[.ps
.pdf]
 A. Jeż, A. Okhotin
Equations over sets of natural numbers with addition only
26th International Symposium on Theoretical Aspects of Computer Science (STACS) 2009
[conference,
.ps, .pdf]
 A. Jeż, A. Okhotin
On the computational completeness of equations over sets of natural number
35th International Colloquium on Automata, Languages and Programming (ICALP) (track B) 2008
[.ps,
.pdf,
presentation]
 A. Jeż, A. Okhotin
Complexity
of solutions of equations over sets of natural numbers
25th International Symposium on Theoretical Aspects of Computer Science (STACS)
2008
full version:
Theory of Computing Systems 48:2, 319342 (2011)
[conference,
.ps, .pdf]
 A. Jeż, A. Okhotin
Conjunctive
grammars over a unary alphabet: undecidability and unbounded growth,
2nd International Computer Science Symposium in Russia (CSR) 2007
Best paper in Theory Track award
full version: Theory
of Computing Systems, 46:1 2758 (2010)
[.pdf,
.ps,
presentation]
 A. Jeż
Conjunctive grammars can generate nonregular unary languages
11th Developments in Language Theory (DLT) 2007
full version: International Journal of Foundations of Computer Science
19(3): 597615 (2008)
[presentation]
Online algorithms
Other
 M.
Grech, A. Jeż, A.
Kisielewicz
Graphical
complexity of products of permutation groups
Discrete
Mathematics 308 (2008), 11421152.
[available on request]
 A. Jeż, P. Śniady
Generalised
Cauchy identities, trees and multidimensional Brownian motions. Part
II: Combinatorial differential calculus
[arXiv]
 October 2010
PhD thesis Conjunctive Grammars and Equations over Sets of Natural Numbers
defended 14 IX 2010