Author name cluster

Artur Jeż

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

Highlights Conference 2024 Conference Abstract

What's new in word equations

Artur Jeż

A word equation is a formal equation using words (also called strings), variables (representing words) and concatenation as the only allowed operation, i. e. they are of the form u = v, where u, v consists of letters and variables. A solution substitutes variables with words so that this formal equality is turned into true equality of strings. Often we also allow usage of additional constraints, say we require that a substitution for a variable is from a certain regular language or that lengths of substitutions satisfy some linear inequality, etc. In this talk I will present state of the art, some recent results and directions on word equations: what is known about satisfiability and major techniques that are used, this will include some restricted classes of equations, including some recent upper bounds of NP for subclasses of quadratic equations. what is known about the solution sets, this includes recent result bounding the number of solutions of equations using one variable only. detail a new trend in application of word equations in verification, usually referred as string solving, this will also include some gentle introduction to fragments of logics over word equations and some smaller, particular results.

Details

TCS Journal 2017 Journal Article

Unambiguous conjunctive grammars over a one-symbol alphabet

Artur Jeż
Alexander Okhotin

It is demonstrated that unambiguous conjunctive grammars over a unary alphabet Σ = { a } have non-trivial expressive power, and that their basic properties are undecidable. The key result is that for every base of positional notation, k ⩾ 11, and for every one-way real-time cellular automaton operating over the alphabet of base-k digits between ⌊ k + 9 4 ⌋ and ⌊ k + 1 2 ⌋, the language of all strings a n with the base-k representation of the form 1 w 1, where w is accepted by the automaton, is described by an unambiguous conjunctive grammar. Another encoding is used to simulate a cellular automaton in a unary language containing almost all strings. These constructions are used to show that for every fixed unambiguous conjunctive language L 0, testing whether a given unambiguous conjunctive grammar generates L 0 is undecidable.

Details DOI

TCS Journal 2016 Journal Article

A really simple approximation of smallest grammar

Artur Jeż

In this paper we present a really simple linear-time algorithm constructing a context-free grammar of size 4 g log 3 / 2 ⁡ ( N / g ) for the input string, where N is the size of the input string and g the size of the optimal grammar generating this string. The algorithm works for arbitrary size alphabets, but the running time is linear assuming that the alphabet Σ of the input string can be identified with numbers from { 1, …, N c } for some constant c. Algorithms with such an approximation guarantee and running time are known, however all of them were non-trivial and their analyses were involved. The here presented algorithm computes the LZ77 factorisation and transforms it in phases to a grammar. In each phase it maintains an LZ77-like factorisation of the word with at most ℓ factors as well as additional O ( ℓ ) letters, where ℓ was the size of the original LZ77 factorisation. In one phase in a greedy way (by a left-to-right sweep and a help of the factorisation) we choose a set of pairs of consecutive letters to be replaced with new symbols, i. e. nonterminals of the constructed grammar. We choose at least 2/3 of the letters in the word and there are O ( ℓ ) many different pairs among them. Hence there are O ( log ⁡ N ) phases, each of them introduces O ( ℓ ) nonterminals to a grammar. A more precise analysis yields a bound ℓ + 4 ℓ log ⁡ ( N / ℓ ). As ℓ ≤ g, this yields the desired bound g + 4 g log ⁡ ( N / g ).

Details DOI

I&C Journal 2016 Journal Article

Approximation of smallest linear tree grammar

Artur Jeż
Markus Lohrey

A simple linear-time algorithm for constructing a linear context-free tree grammar of size O ( r g + r g log ⁡ ( n / r g ) ) for a given input tree T of size n is presented, where g is the size of a minimal linear context-free tree grammar for T, and r is the maximal rank of symbols in T (which is a constant in many applications). This is the first example of a grammar-based tree compression algorithm with a good, i. e. logarithmic in terms of the size of the input tree, approximation ratio. The analysis of the algorithm uses an extension of the recompression technique from strings to trees.

Details DOI

I&C Journal 2016 Journal Article

Finding all solutions of equations in free groups and monoids with involution

Volker Diekert
Artur Jeż
Wojciech Plandowski

This paper presents a PSPACE algorithm which yields a finite graph of exponential size that describes the set of all solutions of equations in free groups as well as the set of all solutions of equations with rational constraints in free monoids. This became possible due to the recent recompression technique. While this technique was successfully applied for pure word equations without involution or rational constraints it could not be used as a black box for free groups. Actually, the presence of an involution and rational constraints complicates the situation and some additional analysis is necessary. Still, the technique is general enough to accommodate both extensions. In the end, it simplifies proofs that satisfiability of word equations is in PSPACE and the corresponding result for equations in free groups with rational constraints. As a byproduct we can decide in PSPACE whether the solution set is finite.

Details DOI

TCS Journal 2016 Journal Article

Least and greatest solutions of equations over sets of integers

Artur Jeż
Alexander Okhotin

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 | m ∈ S, n ∈ T }. These equations were recently studied by the authors (“Representing hyper-arithmetical sets by equations over sets of integers”, Theory of Computing Systems, 51 (2012), 196–228), and it was shown that the class of sets representable by their unique solutions is exactly the class of hyper-arithmetical sets. In this paper it is demonstrated that greatest solutions of such equations represent exactly the Σ 1 1 -sets in the analytical hierarchy, and all those 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.

Details DOI

TCS Journal 2015 Journal Article

Approximation of grammar-based compression via recompression

Artur Jeż

In this paper we present a simple linear-time algorithm constructing a context-free grammar of size O ( g log ⁡ ( N / g ) ) for the input string, where N is the size of the input string and g the size of the optimal grammar generating this string. The algorithm works for arbitrary size alphabets, but the running time is linear assuming that the alphabet Σ of the input string can be identified with numbers from { 1, …, N c } for some constant c. Otherwise, additional cost of O ( N log ⁡ | Σ | ) is needed. Algorithms with such an approximation guarantee and running time are known, the novelty of this paper is a particular simplicity of the algorithm as well as the analysis of the algorithm, which uses a general technique of recompression recently introduced by the author. Furthermore, contrary to the previous results, this work does not use the LZ representation of the input string in the construction, nor in the analysis.

Details DOI

I&C Journal 2014 Journal Article

Computational completeness of equations over sets of natural numbers

Artur Jeż
Alexander Okhotin

Systems of finitely many equations of the form φ ( X 1, …, X n ) = ψ ( X 1, …, X n ) are considered, in which the unknowns X i are sets of natural numbers, while the expressions φ, ψ may contain singleton constants and the operations of union and pairwise addition S + T = { m + n | m ∈ S, n ∈ T }. It is shown that the family of sets representable by unique (least, greatest) solutions of such systems is exactly the family of recursive (r. e. , co-r. e. , respectively) sets of numbers. Basic decision problems for these systems are located in the arithmetical hierarchy. The same results are established for equations with addition and intersection.

Details DOI

TCS Journal 2013 Journal Article

A ϕ -competitive algorithm for collecting items with increasing weights from a dynamic queue

Marcin Bienkowski
Marek Chrobak
Christoph Dürr
Mathilde Hurand
Artur Jeż
Łukasz Jeż
Grzegorz Stachowiak

The bounded-delay packet scheduling (or buffer management) problem is to schedule transmissions of packets arriving in a buffer of a network link. Each packet has a deadline and a weight associated with it. The objective is to maximize the weight of packets that are transmitted before their deadlines, assuming that only one packet can be transmitted in one time step. Online packet scheduling algorithms have been extensively studied. It is known that no online algorithm can achieve a competitive ratio better than ϕ ≈ 1. 618 (the golden ratio), while the currently best upper bound on the competitive ratio is 2 2 − 1 ≈ 1. 824. Closing the gap between these bounds remains a major open problem. The above mentioned lower bound of ϕ uses instances where item weights increase exponentially over time. In fact, all lower bounds for various versions of buffer management problems involve instances of this type. In this paper, we design an online algorithm for packet scheduling with competitive ratio ϕ when packet weights are increasing, thus matching this lower bound. Our algorithm applies, in fact, to a much more general version of packet scheduling, where only the relative order of the deadlines is known, not their exact values.

Details DOI