Search Results

Documents authored by Jez, Artur

Found 2 Possible Name Variants:

Jez, Artur

Document
DOI: 10.4230/LIPIcs.STACS.2021.30
Solving One Variable Word Equations in the Free Group in Cubic Time

Authors: Robert Ferens and Artur Jeż

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
A word equation with one variable in a free group is given as U = V, where both U and V are words over the alphabet of generators of the free group and X, X⁻¹, for a fixed variable X. An element of the free group is a solution when substituting it for X yields a true equality (interpreted in the free group) of left- and right-hand sides. It is known that the set of all solutions of a given word equation with one variable is a finite union of sets of the form {α wⁱ β : i ∈ ℤ}, where α, w, β are reduced words over the alphabet of generators, and a polynomial-time algorithm (of a high degree) computing this set is known. We provide a cubic time algorithm for this problem, which also shows that the set of solutions consists of at most a quadratic number of the above-mentioned sets. The algorithm uses only simple tools of word combinatorics and group theory and is simple to state. Its analysis is involved and focuses on the combinatorics of occurrences of powers of a word within a larger word.
Cite as

Robert Ferens and Artur Jeż. Solving One Variable Word Equations in the Free Group in Cubic Time. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ferens_et_al:LIPIcs.STACS.2021.30,
  author =	{Ferens, Robert and Je\.{z}, Artur},
  title =	{{Solving One Variable Word Equations in the Free Group in Cubic Time}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.30},
  URN =		{urn:nbn:de:0030-drops-136751},
  doi =		{10.4230/LIPIcs.STACS.2021.30},
  annote =	{Keywords: Word equations, free group, one-variable equations}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CSL.2020.3
Solving Word Equations (And Other Unification Problems) by Recompression (Invited Talk)

Authors: Artur Jeż

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
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; ...).
Cite as

Artur Jeż. Solving Word Equations (And Other Unification Problems) by Recompression (Invited Talk). In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.CSL.2020.3,
  author =	{Je\.{z}, Artur},
  title =	{{Solving Word Equations (And Other Unification Problems) by Recompression}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.3},
  URN =		{urn:nbn:de:0030-drops-116468},
  doi =		{10.4230/LIPIcs.CSL.2020.3},
  annote =	{Keywords: word equation, context unification, equations in groups, compression}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.15
Sliding Windows over Context-Free Languages

Authors: Moses Ganardi, Artur Jez, and Markus Lohrey

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
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).
Cite as

Moses Ganardi, Artur Jez, and Markus Lohrey. Sliding Windows over Context-Free Languages. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.MFCS.2018.15,
  author =	{Ganardi, Moses and Jez, Artur and Lohrey, Markus},
  title =	{{Sliding Windows over Context-Free Languages}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.15},
  URN =		{urn:nbn:de:0030-drops-95973},
  doi =		{10.4230/LIPIcs.MFCS.2018.15},
  annote =	{Keywords: sliding windows, streaming algorithms, context-free languages}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.33
Edit Distance with Block Operations

Authors: Michal Ganczorz, Pawel Gawrychowski, Artur Jez, and Tomasz Kociumaka

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We consider the problem of edit distance in which block operations are allowed, i.e. we ask for the minimal number of (block) operations that are needed to transform a string s to t. We give O(log n) approximation algorithms, where n is the total length of the input strings, for the variants of the problem which allow the following sets of operations: block move; block move and block delete; block move and block copy; block move, block copy, and block uncopy. The results still hold if we additionally allow any of the following operations: character insert, character delete, block reversal, or block involution (involution is a generalisation of the reversal). Previously, algorithms only for the first and last variant were known, and they had approximation ratios O(log n log^*n) and O(log n (log^*n)^2), respectively. The edit distance with block moves is equivalent, up to a constant factor, to the common string partition problem, in which we are given two strings s, t and the goal is to partition s into minimal number of parts such that they can be permuted in order to obtain t. Thus we also obtain an O(log n) approximation for this problem (compared to the previous O(log n log^* n)). The results use a simplification of the previously used technique of locally consistent parsing, which groups short substrings of a string into phrases so that similar substrings are guaranteed to be grouped in a similar way. Instead of a sophisticated parsing technique relying on a deterministic coin tossing, we use a simple one based on a partition of the alphabet into two subalphabets. In particular, this lowers the running time from O(n log^* n) to O(n). The new algorithms (for block copy or block delete) use a similar algorithm, but the analysis is based on a specially tuned combinatorial function on sets of numbers.
Cite as

Michal Ganczorz, Pawel Gawrychowski, Artur Jez, and Tomasz Kociumaka. Edit Distance with Block Operations. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.ESA.2018.33,
  author =	{Ganczorz, Michal and Gawrychowski, Pawel and Jez, Artur and Kociumaka, Tomasz},
  title =	{{Edit Distance with Block Operations}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.33},
  URN =		{urn:nbn:de:0030-drops-94963},
  doi =		{10.4230/LIPIcs.ESA.2018.33},
  annote =	{Keywords: Edit distance, Block operations, Common string partition}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.95
Word Equations in Nondeterministic Linear Space

Authors: Artur Jez

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Satisfiability of word equations is an important problem in the intersection of formal languages and algebra: Given two sequences consisting of letters and variables we are to decide whether there is a substitution for the variables that turns this equation into true equality of strings. The computational complexity of this problem remains unknown, with the best lower and upper bounds being, respectively, NP and PSPACE. Recently, the novel technique of recompression was applied to this problem, simplifying the known proofs and lowering the space complexity to (nondeterministic) O(n log n). In this paper we show that satisfiability of word equations is in nondeterministic linear space, thus the language of satisfiable word equations is context-sensitive. We use the known recompression-based algorithm and additionally employ Huffman coding for letters. The proof, however, uses analysis of how the fragments of the equation depend on each other as well as a new strategy for nondeterministic choices of the algorithm, which uses several new ideas to limit the space occupied by the letters.
Cite as

Artur Jez. Word Equations in Nondeterministic Linear Space. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 95:1-95:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.ICALP.2017.95,
  author =	{Jez, Artur},
  title =	{{Word Equations in Nondeterministic Linear Space}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{95:1--95:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.95},
  URN =		{urn:nbn:de:0030-drops-74089},
  doi =		{10.4230/LIPIcs.ICALP.2017.95},
  annote =	{Keywords: Word equations, string unification, context-sensitive languages, space efficient computations, linear space}
}
Document
DOI: 10.4230/LIPIcs.CPM.2017.2
Recompression of SLPs

Authors: Artur Jez

Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

Abstract
In this talk I will survey the recompression technique in case of SLPs. The technique is based on applying simple compression operations (replacement of pairs of two different letters by a new letter and replacement of maximal repetition of a letter by a new symbol) to strings represented by SLPs. To this end we modify the SLPs, so that performing such compression operations on SLPs is possible. For instance, when we want to replace ab in the string and SLP has a production X to aY and the string generated by Y is bw, then we alter the rule of Y so that it generates w and replace Y with bY in all rules. In this way the rule becomes X to abY and so ab can be replaced, similar operations are defined for the right sides of the nonterminals. As a result, we are interested mostly in the SLP representation rather than the string itself and its combinatorial properties. What we need to control, though, is the size of the SLP. With appropriate choices of substrings to be compressed it can be shown that it stays linear. The proposed method turned out to be surprisingly efficient and applicable in various scenarios: for instance it can be used to test the equality of SLPs in time O(n log N), where n is the size of the SLP and N the length of the generated string; on the other hand it can be used to approximate the smallest SLP for a given string, with the approximation ratio O(log(n/g)) where n is the length of the string and g the size of the smallest SLP for this string, matching the best known bounds.
Cite as

Artur Jez. Recompression of SLPs. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.CPM.2017.2,
  author =	{Jez, Artur},
  title =	{{Recompression of SLPs}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.2},
  URN =		{urn:nbn:de:0030-drops-73475},
  doi =		{10.4230/LIPIcs.CPM.2017.2},
  annote =	{Keywords: Straight Line Programs, smallest grammar problem, compression, pro- cessing compressed data, recompression}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2017.2
Recompression: New Approach to Word Equations and Context Unification (Invited Talk)

Authors: Artur Jez

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Word equations is given by two strings over disjoint alphabets of letters and variables and we ask whether there is a substitution that satisfies this equation. Recently, a new PSPACE solution to this problem was proposed, it is based on compressing simple substrings of the equation and modifying the equation so that such operations are sound. The analysis focuses on the way the equation is stored and changed rather than on the combinatorics of words. This approach greatly simplified many existing proofs and algorithms. In particular, unlike the previous solutions, it generalises to equations over contexts (known for historical reasons as context unification): contexts are terms with one special symbol that represent a missing argument and they can be applied on terms, in which case their argument replaces the special constant.
Cite as

Artur Jez. Recompression: New Approach to Word Equations and Context Unification (Invited Talk). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 2:1-2:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.STACS.2017.2,
  author =	{Jez, Artur},
  title =	{{Recompression: New Approach to Word Equations and Context Unification}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{2:1--2:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.2},
  URN =		{urn:nbn:de:0030-drops-70280},
  doi =		{10.4230/LIPIcs.STACS.2017.2},
  annote =	{Keywords: Word equations, exponent of periodicity, semantic unification, string unification, context unification, compression}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.35
LZ77 Factorisation of Trees

Authors: Pawel Gawrychowski and Artur Jez

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
We generalise the fundamental concept of LZ77 factorisation from strings to trees. A tree is represented as a collection of edge-disjoint fragments that either consist of one node or has already occurred earlier (in the BFS order). Similarly as for strings, such a collection uniquely determines the tree, so by minimising the number of fragments we obtain a compressed representation of the tree. We show that our generalisation has several useful properties of the standard LZ77 factorisation: it can be computed in polynomial time and its simpler variant in linear time; its size is not larger than the smallest grammar for a tree; it can be transformed (in linear time) into a tree grammar of size O(rg log(n/(rg))), where n is the size of the tree, g the size of the smallest grammar for this tree and r the maximal arity of the nodes in the tree, which matches a recent bound of Jez and Lohrey [STACS 2014], but with a simpler and more modular proof.
Cite as

Pawel Gawrychowski and Artur Jez. LZ77 Factorisation of Trees. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.FSTTCS.2016.35,
  author =	{Gawrychowski, Pawel and Jez, Artur},
  title =	{{LZ77 Factorisation of Trees}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.35},
  URN =		{urn:nbn:de:0030-drops-68700},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.35},
  annote =	{Keywords: Tree grammars, Grammar compression, LZ77, SLP, Tree compression}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.127
Solutions of Word Equations Over Partially Commutative Structures

Authors: Volker Diekert, Artur Jez, and Manfred Kufleitner

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We give NSPACE(n*log(n)) algorithms solving the following decision problems. Satisfiability: Is the given equation over a free partially commutative monoid with involution (resp. a free partially commutative group) solvable? Finiteness: Are there only finitely many solutions of such an equation? PSPACE algorithms with worse complexities for the first problem are known, but so far, a PSPACE algorithm for the second problem was out of reach. Our results are much stronger: Given such an equation, its solutions form an EDT0L language effectively representable in NSPACE(n*log(n)). In particular, we give an effective description of the set of all solutions for equations with constraints in free partially commutative monoids and groups.
Cite as

Volker Diekert, Artur Jez, and Manfred Kufleitner. Solutions of Word Equations Over Partially Commutative Structures. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 127:1-127:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{diekert_et_al:LIPIcs.ICALP.2016.127,
  author =	{Diekert, Volker and Jez, Artur and Kufleitner, Manfred},
  title =	{{Solutions of Word Equations Over Partially Commutative Structures}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{127:1--127:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.127},
  URN =		{urn:nbn:de:0030-drops-62624},
  doi =		{10.4230/LIPIcs.ICALP.2016.127},
  annote =	{Keywords: Word equations, EDT0L language, trace monoid, right-angled Artin group, partial commutation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.445
Approximation of smallest linear tree grammar

Authors: Artur Jez and Markus Lohrey

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
A simple linear-time algorithm for constructing a linear context-free tree grammar of size O(r^2.g.log(n)) 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 an approximation ratio polynomial in g. The analysis of the algorithm uses an extension of the recompression technique (used in the context of grammar-based string compression) from strings to trees.
Cite as

Artur Jez and Markus Lohrey. Approximation of smallest linear tree grammar. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 445-457, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{jez_et_al:LIPIcs.STACS.2014.445,
  author =	{Jez, Artur and Lohrey, Markus},
  title =	{{Approximation of smallest linear tree grammar}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{445--457},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.445},
  URN =		{urn:nbn:de:0030-drops-44789},
  doi =		{10.4230/LIPIcs.STACS.2014.445},
  annote =	{Keywords: Grammar-based compression, Tree compression, Tree-grammars}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.233
Recompression: a simple and powerful technique for word equations

Authors: Artur Jez

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We present an application of a local recompression technique, previously developed by the author in the context of compressed membership problems and compressed pattern matching, to word equations. The technique is based on local modification of variables (replacing X by aX or Xa) and replacement of pairs of letters appearing in the equation by a 'fresh' letter, which can be seen as a bottom-up compression of the solution of the given word equation, to be more specific, building an SLP (Straight-Line Programme) for the solution of the word equation. Using this technique we give new self-contained proofs of many known results for word equations: the presented nondeterministic algorithm runs in O(n log n) space and in time polynomial in log N and n, where N is the size of the length-minimal solution of the word equation. It can be easily generalised to a generator of all solutions of the word equation. A further analysis of the algorithm yields a doubly exponential upper bound on the size of the length-minimal solution. The presented algorithm does not use exponential bound on the exponent of periodicity. Conversely, the analysis of the algorithm yields a new proof of the exponential bound on exponent of periodicity. For O(1) variables with arbitrary many appearances it works in linear space.
Cite as

Artur Jez. Recompression: a simple and powerful technique for word equations. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 233-244, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.STACS.2013.233,
  author =	{Jez, Artur},
  title =	{{Recompression: a simple and powerful technique for word equations}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{233--244},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.233},
  URN =		{urn:nbn:de:0030-drops-39376},
  doi =		{10.4230/LIPIcs.STACS.2013.233},
  annote =	{Keywords: Word equations, exponent of periodicity, string unification}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.136
Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)

Authors: Artur Jez

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
In this paper, a compressed membership problem for finite automata, both deterministic (DFAs) and non-deterministic (NFAs), with compressed transition labels is studied. The compression is represented by straight-line programs (SLPs), i.e. context-free grammars generating exactly one string. A novel technique of dealing with SLPs is introduced: the SLPs are recompressed, so that substrings of the input text are encoded in SLPs labelling the transitions of the NFA (DFA) in the same way, as in the SLP representing the input text. To this end, the SLPs are locally decompressed and then recompressed in a uniform way. Furthermore, in order to reflect the recompression in the NFA, we need to modify it only a little, in particular its size stays polynomial in the input size. Using this technique it is shown that the compressed membership for NFA with compressed labels is in NP, thus confirming the conjecture of Plandowski and Rytter [Plandowski Rytter 1999] and extending the partial result of Lohrey and Mathissen [Lohrey and Mathissen 2011]; as this problem is known to be NP-hard, we settle its exact computational complexity. Moreover, the same technique applied to the compressed membership for DFA with compressed labels yields that this problem is in P, and this problem is known to be P-hard.
Cite as

Artur Jez. Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P). In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 136-147, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.STACS.2012.136,
  author =	{Jez, Artur},
  title =	{{Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{136--147},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.136},
  URN =		{urn:nbn:de:0030-drops-34068},
  doi =		{10.4230/LIPIcs.STACS.2012.136},
  annote =	{Keywords: Compressed membership problem, SLP, Finite Automata, Algorithms for compressed data}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2478
On Equations over Sets of Integers

Authors: Artur Jez and Alexander Okhotin

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition $S+T=\makeset{m+n}{m \in S, \: n \in T}$ and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction $S \dotminus T=\makeset{m-n}{m \in S, \: n \in T, \: m \geqslant n}$. Testing whether a given system has a solution is $\Sigma^1_1$-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.
Cite as

Artur Jez and Alexander Okhotin. On Equations over Sets of Integers. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 477-488, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{jez_et_al:LIPIcs.STACS.2010.2478,
  author =	{Jez, Artur and Okhotin, Alexander},
  title =	{{On Equations over Sets of Integers}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{477--488},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2478},
  URN =		{urn:nbn:de:0030-drops-24780},
  doi =		{10.4230/LIPIcs.STACS.2010.2478},
  annote =	{Keywords: Language equations, computability, arithmetical hierarchy, hyper-arithmetical hierarchy}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1806
Equations over Sets of Natural Numbers with Addition Only

Authors: Artur Jez and Alexander Okhotin

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
Systems of equations of the form $X=YZ$ and $X=C$ are considered, in which the unknowns are sets of natural numbers, ``$+$'' denotes pairwise sum of sets $S+T=\ensuremath{ \{ m+n \: | \: m \in S, \; n \in T \} }$, and $C$ is an ultimately periodic constant. It is shown that such systems are computationally universal, in the sense that for every recursive (r.e., co-r.e.) set $S \subseteq \mathbb{N}$ there exists a system with a unique (least, greatest) solution containing a component $T$ with $S=\ensuremath{ \{ n \: | \: 16n+13 \in T \} }$. This implies undecidability of basic properties of these equations. All results also apply to language equations over a one-letter alphabet with concatenation and regular constants.
Cite as

Artur Jez and Alexander Okhotin. Equations over Sets of Natural Numbers with Addition Only. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 577-588, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{jez_et_al:LIPIcs.STACS.2009.1806,
  author =	{Jez, Artur and Okhotin, Alexander},
  title =	{{Equations over Sets of Natural Numbers with Addition Only}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{577--588},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1806},
  URN =		{urn:nbn:de:0030-drops-18061},
  doi =		{10.4230/LIPIcs.STACS.2009.1806},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1319
Complexity of solutions of equations over sets of natural numbers

Authors: Alexander Okhotin and Artur Jez

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
Systems of equations over sets of natural numbers (or, equivalently, language equations over a one-letter alphabet) of the form $X_i=varphi_i(X_1, ldots, X_n)$ ($1 leqslant i leqslant n$) are considered. Expressions $varphi_i$ may contain the operations of union, intersection and pairwise sum $A plus B = {x + y mid x in A, y in B$. A system with an EXPTIME-complete least solution is constructed, and it is established that least solutions of all such systems are in EXPTIME. The general membership problem for these equations is proved to be EXPTIME-complete.
Cite as

Alexander Okhotin and Artur Jez. Complexity of solutions of equations over sets of natural numbers. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 373-384, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{okhotin_et_al:LIPIcs.STACS.2008.1319,
  author =	{Okhotin, Alexander and Jez, Artur},
  title =	{{Complexity of solutions of equations  over sets of natural numbers}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{373--384},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1319},
  URN =		{urn:nbn:de:0030-drops-13194},
  doi =		{10.4230/LIPIcs.STACS.2008.1319},
  annote =	{Keywords: }
}

Jeż, Artur

Document
DOI: 10.4230/LIPIcs.STACS.2021.30
Solving One Variable Word Equations in the Free Group in Cubic Time

Authors: Robert Ferens and Artur Jeż

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
A word equation with one variable in a free group is given as U = V, where both U and V are words over the alphabet of generators of the free group and X, X⁻¹, for a fixed variable X. An element of the free group is a solution when substituting it for X yields a true equality (interpreted in the free group) of left- and right-hand sides. It is known that the set of all solutions of a given word equation with one variable is a finite union of sets of the form {α wⁱ β : i ∈ ℤ}, where α, w, β are reduced words over the alphabet of generators, and a polynomial-time algorithm (of a high degree) computing this set is known. We provide a cubic time algorithm for this problem, which also shows that the set of solutions consists of at most a quadratic number of the above-mentioned sets. The algorithm uses only simple tools of word combinatorics and group theory and is simple to state. Its analysis is involved and focuses on the combinatorics of occurrences of powers of a word within a larger word.
Cite as

Robert Ferens and Artur Jeż. Solving One Variable Word Equations in the Free Group in Cubic Time. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ferens_et_al:LIPIcs.STACS.2021.30,
  author =	{Ferens, Robert and Je\.{z}, Artur},
  title =	{{Solving One Variable Word Equations in the Free Group in Cubic Time}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.30},
  URN =		{urn:nbn:de:0030-drops-136751},
  doi =		{10.4230/LIPIcs.STACS.2021.30},
  annote =	{Keywords: Word equations, free group, one-variable equations}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CSL.2020.3
Solving Word Equations (And Other Unification Problems) by Recompression (Invited Talk)

Authors: Artur Jeż

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
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; ...).
Cite as

Artur Jeż. Solving Word Equations (And Other Unification Problems) by Recompression (Invited Talk). In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.CSL.2020.3,
  author =	{Je\.{z}, Artur},
  title =	{{Solving Word Equations (And Other Unification Problems) by Recompression}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.3},
  URN =		{urn:nbn:de:0030-drops-116468},
  doi =		{10.4230/LIPIcs.CSL.2020.3},
  annote =	{Keywords: word equation, context unification, equations in groups, compression}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.15
Sliding Windows over Context-Free Languages

Authors: Moses Ganardi, Artur Jez, and Markus Lohrey

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
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).
Cite as

Moses Ganardi, Artur Jez, and Markus Lohrey. Sliding Windows over Context-Free Languages. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.MFCS.2018.15,
  author =	{Ganardi, Moses and Jez, Artur and Lohrey, Markus},
  title =	{{Sliding Windows over Context-Free Languages}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.15},
  URN =		{urn:nbn:de:0030-drops-95973},
  doi =		{10.4230/LIPIcs.MFCS.2018.15},
  annote =	{Keywords: sliding windows, streaming algorithms, context-free languages}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.33
Edit Distance with Block Operations

Authors: Michal Ganczorz, Pawel Gawrychowski, Artur Jez, and Tomasz Kociumaka

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We consider the problem of edit distance in which block operations are allowed, i.e. we ask for the minimal number of (block) operations that are needed to transform a string s to t. We give O(log n) approximation algorithms, where n is the total length of the input strings, for the variants of the problem which allow the following sets of operations: block move; block move and block delete; block move and block copy; block move, block copy, and block uncopy. The results still hold if we additionally allow any of the following operations: character insert, character delete, block reversal, or block involution (involution is a generalisation of the reversal). Previously, algorithms only for the first and last variant were known, and they had approximation ratios O(log n log^*n) and O(log n (log^*n)^2), respectively. The edit distance with block moves is equivalent, up to a constant factor, to the common string partition problem, in which we are given two strings s, t and the goal is to partition s into minimal number of parts such that they can be permuted in order to obtain t. Thus we also obtain an O(log n) approximation for this problem (compared to the previous O(log n log^* n)). The results use a simplification of the previously used technique of locally consistent parsing, which groups short substrings of a string into phrases so that similar substrings are guaranteed to be grouped in a similar way. Instead of a sophisticated parsing technique relying on a deterministic coin tossing, we use a simple one based on a partition of the alphabet into two subalphabets. In particular, this lowers the running time from O(n log^* n) to O(n). The new algorithms (for block copy or block delete) use a similar algorithm, but the analysis is based on a specially tuned combinatorial function on sets of numbers.
Cite as

Michal Ganczorz, Pawel Gawrychowski, Artur Jez, and Tomasz Kociumaka. Edit Distance with Block Operations. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.ESA.2018.33,
  author =	{Ganczorz, Michal and Gawrychowski, Pawel and Jez, Artur and Kociumaka, Tomasz},
  title =	{{Edit Distance with Block Operations}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.33},
  URN =		{urn:nbn:de:0030-drops-94963},
  doi =		{10.4230/LIPIcs.ESA.2018.33},
  annote =	{Keywords: Edit distance, Block operations, Common string partition}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.95
Word Equations in Nondeterministic Linear Space

Authors: Artur Jez

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Satisfiability of word equations is an important problem in the intersection of formal languages and algebra: Given two sequences consisting of letters and variables we are to decide whether there is a substitution for the variables that turns this equation into true equality of strings. The computational complexity of this problem remains unknown, with the best lower and upper bounds being, respectively, NP and PSPACE. Recently, the novel technique of recompression was applied to this problem, simplifying the known proofs and lowering the space complexity to (nondeterministic) O(n log n). In this paper we show that satisfiability of word equations is in nondeterministic linear space, thus the language of satisfiable word equations is context-sensitive. We use the known recompression-based algorithm and additionally employ Huffman coding for letters. The proof, however, uses analysis of how the fragments of the equation depend on each other as well as a new strategy for nondeterministic choices of the algorithm, which uses several new ideas to limit the space occupied by the letters.
Cite as

Artur Jez. Word Equations in Nondeterministic Linear Space. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 95:1-95:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.ICALP.2017.95,
  author =	{Jez, Artur},
  title =	{{Word Equations in Nondeterministic Linear Space}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{95:1--95:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.95},
  URN =		{urn:nbn:de:0030-drops-74089},
  doi =		{10.4230/LIPIcs.ICALP.2017.95},
  annote =	{Keywords: Word equations, string unification, context-sensitive languages, space efficient computations, linear space}
}
Document
DOI: 10.4230/LIPIcs.CPM.2017.2
Recompression of SLPs

Authors: Artur Jez

Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

Abstract
In this talk I will survey the recompression technique in case of SLPs. The technique is based on applying simple compression operations (replacement of pairs of two different letters by a new letter and replacement of maximal repetition of a letter by a new symbol) to strings represented by SLPs. To this end we modify the SLPs, so that performing such compression operations on SLPs is possible. For instance, when we want to replace ab in the string and SLP has a production X to aY and the string generated by Y is bw, then we alter the rule of Y so that it generates w and replace Y with bY in all rules. In this way the rule becomes X to abY and so ab can be replaced, similar operations are defined for the right sides of the nonterminals. As a result, we are interested mostly in the SLP representation rather than the string itself and its combinatorial properties. What we need to control, though, is the size of the SLP. With appropriate choices of substrings to be compressed it can be shown that it stays linear. The proposed method turned out to be surprisingly efficient and applicable in various scenarios: for instance it can be used to test the equality of SLPs in time O(n log N), where n is the size of the SLP and N the length of the generated string; on the other hand it can be used to approximate the smallest SLP for a given string, with the approximation ratio O(log(n/g)) where n is the length of the string and g the size of the smallest SLP for this string, matching the best known bounds.
Cite as

Artur Jez. Recompression of SLPs. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.CPM.2017.2,
  author =	{Jez, Artur},
  title =	{{Recompression of SLPs}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.2},
  URN =		{urn:nbn:de:0030-drops-73475},
  doi =		{10.4230/LIPIcs.CPM.2017.2},
  annote =	{Keywords: Straight Line Programs, smallest grammar problem, compression, pro- cessing compressed data, recompression}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2017.2
Recompression: New Approach to Word Equations and Context Unification (Invited Talk)

Authors: Artur Jez

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Word equations is given by two strings over disjoint alphabets of letters and variables and we ask whether there is a substitution that satisfies this equation. Recently, a new PSPACE solution to this problem was proposed, it is based on compressing simple substrings of the equation and modifying the equation so that such operations are sound. The analysis focuses on the way the equation is stored and changed rather than on the combinatorics of words. This approach greatly simplified many existing proofs and algorithms. In particular, unlike the previous solutions, it generalises to equations over contexts (known for historical reasons as context unification): contexts are terms with one special symbol that represent a missing argument and they can be applied on terms, in which case their argument replaces the special constant.
Cite as

Artur Jez. Recompression: New Approach to Word Equations and Context Unification (Invited Talk). In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 2:1-2:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.STACS.2017.2,
  author =	{Jez, Artur},
  title =	{{Recompression: New Approach to Word Equations and Context Unification}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{2:1--2:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.2},
  URN =		{urn:nbn:de:0030-drops-70280},
  doi =		{10.4230/LIPIcs.STACS.2017.2},
  annote =	{Keywords: Word equations, exponent of periodicity, semantic unification, string unification, context unification, compression}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.35
LZ77 Factorisation of Trees

Authors: Pawel Gawrychowski and Artur Jez

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
We generalise the fundamental concept of LZ77 factorisation from strings to trees. A tree is represented as a collection of edge-disjoint fragments that either consist of one node or has already occurred earlier (in the BFS order). Similarly as for strings, such a collection uniquely determines the tree, so by minimising the number of fragments we obtain a compressed representation of the tree. We show that our generalisation has several useful properties of the standard LZ77 factorisation: it can be computed in polynomial time and its simpler variant in linear time; its size is not larger than the smallest grammar for a tree; it can be transformed (in linear time) into a tree grammar of size O(rg log(n/(rg))), where n is the size of the tree, g the size of the smallest grammar for this tree and r the maximal arity of the nodes in the tree, which matches a recent bound of Jez and Lohrey [STACS 2014], but with a simpler and more modular proof.
Cite as

Pawel Gawrychowski and Artur Jez. LZ77 Factorisation of Trees. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.FSTTCS.2016.35,
  author =	{Gawrychowski, Pawel and Jez, Artur},
  title =	{{LZ77 Factorisation of Trees}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{35:1--35:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.35},
  URN =		{urn:nbn:de:0030-drops-68700},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.35},
  annote =	{Keywords: Tree grammars, Grammar compression, LZ77, SLP, Tree compression}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.127
Solutions of Word Equations Over Partially Commutative Structures

Authors: Volker Diekert, Artur Jez, and Manfred Kufleitner

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We give NSPACE(n*log(n)) algorithms solving the following decision problems. Satisfiability: Is the given equation over a free partially commutative monoid with involution (resp. a free partially commutative group) solvable? Finiteness: Are there only finitely many solutions of such an equation? PSPACE algorithms with worse complexities for the first problem are known, but so far, a PSPACE algorithm for the second problem was out of reach. Our results are much stronger: Given such an equation, its solutions form an EDT0L language effectively representable in NSPACE(n*log(n)). In particular, we give an effective description of the set of all solutions for equations with constraints in free partially commutative monoids and groups.
Cite as

Volker Diekert, Artur Jez, and Manfred Kufleitner. Solutions of Word Equations Over Partially Commutative Structures. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 127:1-127:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{diekert_et_al:LIPIcs.ICALP.2016.127,
  author =	{Diekert, Volker and Jez, Artur and Kufleitner, Manfred},
  title =	{{Solutions of Word Equations Over Partially Commutative Structures}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{127:1--127:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.127},
  URN =		{urn:nbn:de:0030-drops-62624},
  doi =		{10.4230/LIPIcs.ICALP.2016.127},
  annote =	{Keywords: Word equations, EDT0L language, trace monoid, right-angled Artin group, partial commutation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.445
Approximation of smallest linear tree grammar

Authors: Artur Jez and Markus Lohrey

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
A simple linear-time algorithm for constructing a linear context-free tree grammar of size O(r^2.g.log(n)) 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 an approximation ratio polynomial in g. The analysis of the algorithm uses an extension of the recompression technique (used in the context of grammar-based string compression) from strings to trees.
Cite as

Artur Jez and Markus Lohrey. Approximation of smallest linear tree grammar. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 445-457, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{jez_et_al:LIPIcs.STACS.2014.445,
  author =	{Jez, Artur and Lohrey, Markus},
  title =	{{Approximation of smallest linear tree grammar}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{445--457},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.445},
  URN =		{urn:nbn:de:0030-drops-44789},
  doi =		{10.4230/LIPIcs.STACS.2014.445},
  annote =	{Keywords: Grammar-based compression, Tree compression, Tree-grammars}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.233
Recompression: a simple and powerful technique for word equations

Authors: Artur Jez

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We present an application of a local recompression technique, previously developed by the author in the context of compressed membership problems and compressed pattern matching, to word equations. The technique is based on local modification of variables (replacing X by aX or Xa) and replacement of pairs of letters appearing in the equation by a 'fresh' letter, which can be seen as a bottom-up compression of the solution of the given word equation, to be more specific, building an SLP (Straight-Line Programme) for the solution of the word equation. Using this technique we give new self-contained proofs of many known results for word equations: the presented nondeterministic algorithm runs in O(n log n) space and in time polynomial in log N and n, where N is the size of the length-minimal solution of the word equation. It can be easily generalised to a generator of all solutions of the word equation. A further analysis of the algorithm yields a doubly exponential upper bound on the size of the length-minimal solution. The presented algorithm does not use exponential bound on the exponent of periodicity. Conversely, the analysis of the algorithm yields a new proof of the exponential bound on exponent of periodicity. For O(1) variables with arbitrary many appearances it works in linear space.
Cite as

Artur Jez. Recompression: a simple and powerful technique for word equations. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 233-244, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.STACS.2013.233,
  author =	{Jez, Artur},
  title =	{{Recompression: a simple and powerful technique for word equations}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{233--244},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.233},
  URN =		{urn:nbn:de:0030-drops-39376},
  doi =		{10.4230/LIPIcs.STACS.2013.233},
  annote =	{Keywords: Word equations, exponent of periodicity, string unification}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.136
Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)

Authors: Artur Jez

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
In this paper, a compressed membership problem for finite automata, both deterministic (DFAs) and non-deterministic (NFAs), with compressed transition labels is studied. The compression is represented by straight-line programs (SLPs), i.e. context-free grammars generating exactly one string. A novel technique of dealing with SLPs is introduced: the SLPs are recompressed, so that substrings of the input text are encoded in SLPs labelling the transitions of the NFA (DFA) in the same way, as in the SLP representing the input text. To this end, the SLPs are locally decompressed and then recompressed in a uniform way. Furthermore, in order to reflect the recompression in the NFA, we need to modify it only a little, in particular its size stays polynomial in the input size. Using this technique it is shown that the compressed membership for NFA with compressed labels is in NP, thus confirming the conjecture of Plandowski and Rytter [Plandowski Rytter 1999] and extending the partial result of Lohrey and Mathissen [Lohrey and Mathissen 2011]; as this problem is known to be NP-hard, we settle its exact computational complexity. Moreover, the same technique applied to the compressed membership for DFA with compressed labels yields that this problem is in P, and this problem is known to be P-hard.
Cite as

Artur Jez. Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P). In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 136-147, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.STACS.2012.136,
  author =	{Jez, Artur},
  title =	{{Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{136--147},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.136},
  URN =		{urn:nbn:de:0030-drops-34068},
  doi =		{10.4230/LIPIcs.STACS.2012.136},
  annote =	{Keywords: Compressed membership problem, SLP, Finite Automata, Algorithms for compressed data}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2478
On Equations over Sets of Integers

Authors: Artur Jez and Alexander Okhotin

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition $S+T=\makeset{m+n}{m \in S, \: n \in T}$ and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction $S \dotminus T=\makeset{m-n}{m \in S, \: n \in T, \: m \geqslant n}$. Testing whether a given system has a solution is $\Sigma^1_1$-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.
Cite as

Artur Jez and Alexander Okhotin. On Equations over Sets of Integers. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 477-488, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{jez_et_al:LIPIcs.STACS.2010.2478,
  author =	{Jez, Artur and Okhotin, Alexander},
  title =	{{On Equations over Sets of Integers}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{477--488},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2478},
  URN =		{urn:nbn:de:0030-drops-24780},
  doi =		{10.4230/LIPIcs.STACS.2010.2478},
  annote =	{Keywords: Language equations, computability, arithmetical hierarchy, hyper-arithmetical hierarchy}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1806
Equations over Sets of Natural Numbers with Addition Only

Authors: Artur Jez and Alexander Okhotin

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
Systems of equations of the form $X=YZ$ and $X=C$ are considered, in which the unknowns are sets of natural numbers, ``$+$'' denotes pairwise sum of sets $S+T=\ensuremath{ \{ m+n \: | \: m \in S, \; n \in T \} }$, and $C$ is an ultimately periodic constant. It is shown that such systems are computationally universal, in the sense that for every recursive (r.e., co-r.e.) set $S \subseteq \mathbb{N}$ there exists a system with a unique (least, greatest) solution containing a component $T$ with $S=\ensuremath{ \{ n \: | \: 16n+13 \in T \} }$. This implies undecidability of basic properties of these equations. All results also apply to language equations over a one-letter alphabet with concatenation and regular constants.
Cite as

Artur Jez and Alexander Okhotin. Equations over Sets of Natural Numbers with Addition Only. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 577-588, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{jez_et_al:LIPIcs.STACS.2009.1806,
  author =	{Jez, Artur and Okhotin, Alexander},
  title =	{{Equations over Sets of Natural Numbers with Addition Only}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{577--588},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1806},
  URN =		{urn:nbn:de:0030-drops-18061},
  doi =		{10.4230/LIPIcs.STACS.2009.1806},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1319
Complexity of solutions of equations over sets of natural numbers

Authors: Alexander Okhotin and Artur Jez

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
Systems of equations over sets of natural numbers (or, equivalently, language equations over a one-letter alphabet) of the form $X_i=varphi_i(X_1, ldots, X_n)$ ($1 leqslant i leqslant n$) are considered. Expressions $varphi_i$ may contain the operations of union, intersection and pairwise sum $A plus B = {x + y mid x in A, y in B$. A system with an EXPTIME-complete least solution is constructed, and it is established that least solutions of all such systems are in EXPTIME. The general membership problem for these equations is proved to be EXPTIME-complete.
Cite as

Alexander Okhotin and Artur Jez. Complexity of solutions of equations over sets of natural numbers. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 373-384, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{okhotin_et_al:LIPIcs.STACS.2008.1319,
  author =	{Okhotin, Alexander and Jez, Artur},
  title =	{{Complexity of solutions of equations  over sets of natural numbers}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{373--384},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1319},
  URN =		{urn:nbn:de:0030-drops-13194},
  doi =		{10.4230/LIPIcs.STACS.2008.1319},
  annote =	{Keywords: }
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact