Artur Jez

CSL Conference 2020 Conference Paper

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

• Artur Jez

In word equation problem we are given an equation u = v, where both u and v are words of letters and variables, and ask for a substitution of variables by words that equalizes the sides of the equation. This problem was first solved by Makanin and a different solution was proposed by Plandowski only 20 years later, his solution works in PSPACE, which is the best computational complexity bound known for this problem; on the other hand, the only known lower-bound is NP-hardness. In both cases the algorithms (and proofs) employed nontrivial facts on word combinatorics. In the paper I will present an application of a recent technique of recompression, which simplifies the known proofs and (slightly) lowers the complexity to linear nondeterministic space. The technique is based on employing simple compression rules (replacement of two letters ab by a new letter c, replacement of maximal repetitions of a by a new letter), and modifying the equations (replacing a variable X by bX or Xa) so that those operations are sound and complete. In particular, no combinatorial properties of strings are used. The approach turns out to be quite robust and can be applied to various generalizations and related scenarios (context unification, i. e. equations over terms; equations over traces, i. e. partially ordered words; .. .).

FOCS Conference 2019 Conference Paper

Balancing Straight-Line Programs

• Moses Ganardi
• Artur Jez
• Markus Lohrey

We show that a context-free grammar of size m that produces a single string w of length n (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar for w of size O(m), whose unique derivation tree has depth O(log n). This solves an open problem in the area of grammar-based compression, improves many results in this area and greatly simplifies many existing constructions. Similar results are stated for two formalisms for grammar-based tree compression: top dags and forest straight-line programs. These balancing results can be all deduced from a single meta theorem stating that the depth of an algebraic circuit over an algebra with a certain finite base property can be reduced to O(log n) with the cost of a constant multiplicative size increase. Here, n refers to the size of the unfolding (or unravelling) of the circuit. In particular, this results applies to standard arithmetic circuits over (non-commutative) semirings. A long version of the paper can be found in [1].

MFCS Conference 2018 Conference Paper

Sliding Windows over Context-Free Languages

• Moses Ganardi
• Artur Jez
• Markus Lohrey

We study the space complexity of sliding window streaming algorithms that check membership of the window content in a fixed context-free language. For regular languages, this complexity is either constant, logarithmic or linear [Moses Ganardi et al. , 2016]. We prove that every context-free language whose sliding window space complexity is log_2(n) - omega(1) must be regular and has constant space complexity. Moreover, for every c in N, c >= 1 we construct a (nondeterministic) context-free language whose sliding window space complexity is O(n^(1/c)) \ o(n^(1/c)). Finally, we give an example of a deterministic one-counter language whose sliding window space complexity is Theta((log n)^2).

MFCS Conference 2011 Conference Paper

On Minimising Automata with Errors

• Pawel Gawrychowski
• Artur Jez
• Andreas Maletti

Abstract The problem of k -minimisation for a DFA M is the computation of a smallest DFA N (where the size | M | of a DFA M is the size of the domain of the transition function) such that L ( M ) Δ L ( N ) ⊆ Σ < k, which means that their recognized languages differ only on words of length less than k. The previously best algorithm, which runs in time \(\mathcal{O}(\mid M \mid{\rm log}^{2} n)\) where n is the number of states, is extended to DFAs with partial transition functions. Moreover, a faster \(\mathcal{O}(\mid M \mid\log n)\) algorithm for DFAs that recognise finite languages is presented. In comparison to the previous algorithm for total DFAs, the new algorithm is much simpler and allows the calculation of a k -minimal DFA for each k in parallel. Secondly, it is demonstrated that calculating the least number of introduced errors is hard: Given a DFA M and numbers k and m, it is NP-hard to decide whether there exists a k -minimal DFA N with | L ( M ) Δ L ( N ) ≤ m. A similar result holds for hyper-minimisation of DFAs in general: Given a DFA M and numbers s and m, it is NP-hard to decide whether there exists a DFA N with at most s states such that | L ( M ) Δ L ( N ) ≤ m.

MFCS Conference 2010 Conference Paper

Least and Greatest Solutions of Equations over Sets of Integers

• Artur Jez
• Alexander Okhotin

Abstract Systems of equations with sets of integers as unknowns are considered, with the operations of union, intersection and addition of sets, \(S+T=\{m+n \mid m \in S, \: n \in T\}\). These equations were recently studied by the authors (“On equations over sets of integers”, STACS 2010 ), and it was shown that their unique solutions represent exactly the hyperarithmetical sets. In this paper it is demonstrated that greatest solutions of such equations represent exactly the \(\Sigma^1_1\) sets in the analytical hierarchy, and these sets can already be represented by systems in the resolved form X i = ϕ i ( X 1, .. ., X n ). Least solutions of such resolved systems represent exactly the recursively enumerable sets.

SODA Conference 2009 Conference Paper

Collecting weighted items from a dynamic queue

• Marcin Bienkowski
• Marek Chrobak
• Christoph Dürr
• Mathilde Hurand
• Artur Jez
• Lukasz Jez
• Grzegorz Stachowiak

MFCS Conference 2009 Conference Paper

Hyper-minimisation Made Efficient

• Pawel Gawrychowski
• Artur Jez

Abstract We consider a problem of hyper-minimisation of an automaton [2, 3]: given a DFA M we want to compute a smallest automaton N such that the language L ( M ) Δ L ( N ) is finite, where Δ denotes the symmetric difference. We improve the previously known \(\mathcal O (|\Sigma|n^2)\) solution by giving an expected \(\mathcal O (|\delta|\log n)\) time algorithm for this problem, where | δ | is the size of the (potentially partial) transition function. We also give a slightly slower deterministic \(\mathcal O(|\delta|\log^2 n)\) version of the algorithm. Then we introduce a similar problem of k -minimisation: for an automaton M and number k we want to find a smallest automaton N such that L ( M ) Δ L ( N ) ⊆ Σ < k, i. e. the languages they recognize differ only on words of length less than k. We characterise such minimal automata and give algorithm with a similar complexity for this problem.