Artur Jeż

Office no. 342
Instytut Informatyki
ul. Joliot-Curie 15
PL-50-383 Wrocław
Poland

Email: aje X cs.uni.wroc.pl
tel +48 71 375-78-37
fax +48 71 375-78-01

Teaching and office hours (mostly in Polish)

Papers

Systems of Equations over Sets of Numbers

• 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, 329-348 (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: Theory of Computing Systems (available online)
  [.pdf, presentation]
  
  
• A. Jeż, A. Okhotin
  One-nonterminal conjunctive grammars over a unary alphabet
  4th International Computer Science Symposium in Russia (CSR) 2009
  full version: Theory of Computing Systems 49:2, 319-342 (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, 319-342 (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 27-58 (2010)
  [.pdf, .ps, presentation]
  
  
• A. Jeż
  Conjunctive grammars can generate non-regular unary languages
  11th Developments in Language Theory (DLT) 2007
  full version: International Journal of Foundations of Computer Science 19(3): 597-615 (2008)
  [.ps, .pdf, presentation]
  

Automata

• A. Jeż, A. Maletti
  Hyper-Minimization 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
  [conference, arXiv]
  
  
• A. Jeż, A. Maletti
  Computing all l-cover 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ż
  Hyper-minimisation made efficient
  34th International Symposiums on Mathematical Foundations of Computer Science (MFCS) 2009
  Best student paper award
  [conference version, rough full version, presentation]
  

String algorithms (and related)

• A. Jeż
  Recompression: a simple and powerful technique for word equations
  [arXiv]
  
  
• A. Jeż
  Faster fully compressed pattern matching by recompression
  39th International Colloquium on Automata, Languages and Programming (ICALP) (track A) 2012
  [arXiv]
  
  
• P. Gawrychowski, A. Jeż, Ł. Jeż
  Validating the Knuth-Morris-Pratt failure function, fast and online
  5th International Computer Science Symposium in Russia (CSR) 2010
  [.ps, .pdf]
  
  

Online algorithms

• M. Bienkowski, M. Chrobak, C. Durr, M. Hurand, A. Jeż, Ł. Jeż, G. Stachowiak
  Collecting Weighted Items from a Dynamic Queue
  Symposium on Discrete Algorithms (SODA) 2009
  full version: Algorithmica (available online)
  [open access]
  
  
• A. Jeż, J. Łopuszański
  On the Two-Dimensional Cow Search Problem
  Information Processing Letters 109 (2009) 543–547
  [.ps]
  

Other

• M. Grech, A. Jeż, A. Kisielewicz
  Graphical complexity of products of permutation groups
  Discrete Mathematics 308 (2008), 1142-1152.
  [available on request]
  
  
• A. Jeż, P. Śniady
  Generalized Cauchy identities, trees and multidimensional Brownian motions. Part II: Combinatorial differential calculus
  [arXiv]
  

Thesis

• A. Jeż
  Conjunctive Grammars and Equations over Sets of Natural Numbers
  PhD thesis, defended 14 IX 2010
  abstract published in Bulletin of the European Association for Theoretical Computer Science (BEATCS)
  [.ps, .pdf, abstract, short summary, defence presentation]
  

Non-conference 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]