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

Dydaktyka i konsultacje/Teaching and office hours(mostly in Polish)

Editorial boards

Program Committees

Present

• Annual Symposium on Combinatorial Pattern Matching (CPM) 25.06–27.06.2024, Fukuoka, Japan.

Past

• Latin American Symposium on Theoretical Informatics (LATIN) 2024, Puerto Varas, Chile
• International Symposium on Fundamentals of Computation Theory (FCT) 2023, Trier, Germany
• International Conference on Developments in Language Theory (DLT) 2022, Tampa, Florida, USA.
• ICALP 2022 satellite workshop Straight-Line Programs, Word Equations and their Interplay 2022 Paris, France
• International Symposium on Mathematical Foundations of Computer Science (MFCS) 2020, Prague, Czech Republic
• Annual Symposium on Combinatorial Pattern Matching (CPM) 2020, Copenhagen, Denmark
• International Workshop on Combinatorial Algorithms (IWOCA) 2019, Pisa, Italy
• International Conference on Implementation and Application of Automata (CIAA) 2019, Košice, Slovakia
• International Conference on Grammatical Inference (ICGI) 2018, Wrocław, Poland
• Latin American Symposium on Theoretical Informatics (LATIN) 2018, Buenos Aires, Argentina
• International Conference on Developments in Language Theory (DLT) 2017, Liege, Belgium.
• International Symposium on String Processing and Information Retrieval (SPIRE) 2017, Palermo, Italy.
• International Workshop on Unification (UNIF) 2017, Oxford, UK.
• 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.
• 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.

Grants (as a PI)

Past

• Polish National Science Centre (NCN) SONATA BIS grant 2017/26/E/ST6/00191 2018–23
  Aspects of grammar compression
• Polish National Science Centre (NCN) OPUS grant 2014/15/B/ST6/00615 2015–18
  Compression, logic, formal languages: new approaches unifying different areas
• Polish National Science Centre (NCN) SONATA grant 2011/01/D/ST6/07164 2011–15
  Efficient algorithms and representations in formal languages and automata theory
• Polish Ministry of Higher Eduction and Science (MNiSW) PhD grant N N206 2590 35 2008–10
  Conjunctive grammars and systems of equations over sets of numbers
  (de iure not a PI, but de facto a PI)

Publications

• A. Jeż, A. W. Lin, M. Hague Parikh's Theorem Made Symbolic POPL 2024 [conference version, arXiv]
• A. Jeż, A. W. Lin, O. Markgraf, Ph. Rümmer Decision Procedures for Sequence Theories CAV 2023 [conference version, arXiv]
• D. Figueira, A. Jeż, A. W. Lin Data Path Queries over Embedded Graph Databases PODS 2022 [conference version]
• R. Ferens, A. Jeż Solving one variable word equations in the free group in cubic time STACS 2021 [arXiv]
• H. Bannai, M. Hirayama, D. Hucke, S. Inenaga, A. Jeż, M. Lohrey, C. Reh The Smallest Grammar Problem Revisited IEEE Transactions on Information Theory [arXiv, journal]
• M. Ganardi, A. Jeż, M. Lohrey Balancing Straight-Line Programs FOCS 2019, full version: Journal of the ACM [arXiv, journal version]
• M. Gańczorz, P. Gawrychowski, A. Jeż, T. Kociumaka Edit Distance with Block Operations ESA 2018 [conference version]
• M. Ganardi, Artur Jez, M. Lohrey Sliding Windows over Context-Free Languages MFCS 2018 [conference version]
• A. Jeż Word Equations in Nondeterministic Linear Space ICALP (B) 2017 full version Journal of Computer and System Sciences[conference version, arXiv, presentation, long and technical presentation, journal version]
• M. Gańczorz, A. Jeż Improvements on Re-Pair Grammar Compressor. DCC 2017
• M. Ganardi, D. Hucke, A. Jeż, M. Lohrey, E. Noeth Constructing small tree grammars and small circuits for formulas Journal of Computer Systems and Sciences 86: 136-158 (2017). [.pdf]
• V. Diekert, A. Jeż, M. Kufleitner Solutions of Word Equations Over Partially Commutative Structures ICALP (B) 2016 [arXiv, conference version]
• P. Gawrychowski, A. Jez LZ77 Factorisation of Trees. FSTTCS 2016 35:1-35:15 [conference version]
• A. Jeż Context unification is in PSPACE ICALP (B) 2014 full version: Deciding context unification, Journal of the ACM [journal, 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ż One-variable 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 Grammar-Based 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ż, A. Okhotin Unambiguous Conjunctive Grammars over a One-Letter Alphabet 17th Internation Conference on Developments in Language Theory (DLT) 2013 full version: Theoretical Computer Science 665: 13–39 (2017)
• 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]
• A. Jeż, A. Maletti Hyper-Minimiżation for Deterministic Tree Automata 17th International Conference on Implementation and Application of Automata (CIAA) 2012
• 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 full version: Fundamenta Informaticae 162(1):43–72 (2018)
• 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] 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 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 Hyper-arithmetical Sets by Equations over Sets of Integers Theory of Computing Systems, 51:2, 196-228 (2012) [.pdf, presentation]
• P. Gawrychowski, A. Jeż, Ł. Jeż Validating the Knuth-Morris-Pratt failure function, fast and online 5th International Computer Science Symposium in Russia (CSR) 2010 full version: Theory of Computing Systems [journal, presentation]
• 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]
• 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 full version: Information and Computation [conference, .ps, .pdf]
• 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 split into: Algorithmica and Theoretical Computer Science [open access, tcs]
• A. Jeż, J. Łopuszański On the Two-Dimensional Cow Search Problem Information Processing Letters 109 (2009) 543–547 [.ps]
• 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, 319-342 (2011) [conference, .ps, .pdf]
• M. Grech, A. Jeż, A. Kisielewicz Graphical complexity of products of permutation groups Discrete Mathematics 308 (2008), 1142-1152. [available on request]
• 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) [presentation]
• A. Jeż, P. Śniady Generalised 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]