Artur Jeż
Office no. 342
Instytut Informatyki
ul. JoliotCurie 15
PL50383 Wrocław
Poland
Email: aje X cs.uni.wroc.pl
tel +48 71 3757837
fax +48 71 3757801
Present
Past
 Descriptional Complexity of Formal Systems (DCFS) 2015, Waterloo, Ontario, Canada.
 International Conference on Developments in Language Theory (DLT) 2015, Liverpool, UK.
 International Workshop on Unification (UNIF) 2015, Warsaw, Poland.
 International Symposium on Theoretical Aspects of Computer Science (STACS) 2016, Orleans, France.
 International Symposium on Mathematical Foundations of Computer Science (MFCS) 2016, Kraków, Poland.
 International Workshop on Unification (UNIF) 2016, Milano, Italy.
Grants
Present
Recompression

V. Diekert, A. Jeż, M. Kufleitner
Solutions of Word Equations Over Partially Commutative Structures
43rd International Colloquium on Automata, Languages and Programming (ICALP (B)) 2016
[arXiv, conference version]
 A. Jeż
Context unification is in PSPACE
41st International Colloquium on Automata, Languages and Programming (ICALP (B)) 2014
[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 2014
full version: Information and Computation
[arXiv]
 A. Jeż
A really simple approximation of smallest grammar
25th Annual Symposium on Combinatorial Pattern Matching (CPM) 2014
full version: Theoretical Computer Science
[arXiv, presentation]
 A. Jeż, M. Lohrey
Approximation of smallest linear tree grammar
31st International Symposium on Theoretical Aspects of Computer Science (STACS) 2014
full version: Information and Computation
[arXiv, presentation]
 A. Jeż
Onevariable word equations in linear time
40th International Colloquium on Automata, Languages and Programming (ICALP) (track B) 2013
full version: Algorithmica
[journal, 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
full version: Theoretical Computer Science
[arXiv, presentation]
 A. Jeż
Recompression: a simple and powerful technique for word equations
30th International Symposium on Theoretical Aspects of Computer Science (STACS) 2013
full version: Journal of the ACM
[journal, 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
full version: ACM Transactions on Algorithms
[journal, arXiv, presentation]

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: The Complexity of Compressed Membership Problems for Finite Automata Theory of Computing Systems
[conference, arXiv,
presentation,
journal]
Hyperminimisation and related
 A. Jeż, A. Maletti
HyperMinimiżation for Deterministic Tree Automata
17th International Conference on Implementation and Application of Automata (CIAA) 2012
 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
full version: Theoretical Computer Science
[.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
full version: Information and Computation
[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
full version: Information and Computation
[.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]
 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
[journal, presentation]
Thesis
Nonconference Presentations
 Jak matematyka pomaga w wyszukiwanie wzorca
Wrocław 28 IX 2011
[.pdf]
 Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)
Turku 7 IX 2011
[.pdf]
 Układy
równań nad zbiorami liczb naturalnych
Wrocław 14 IX 2010
[.pdf]
 Equations in sets of natural numbers
Brno 22 V 2008
[.pdf]
 Równania nad zbiorami liczb naturalnych
FIT 2008
[.pdf]
 Equations in sets of natural numbers
Turku 13 XII 2007
[.pdf]