Wojciech Plandowski

TCS Journal 2019 Journal Article

On PSPACE generation of a solution set of a word equation and its applications

• Wojciech Plandowski

There are three approaches to solve satisfiability problem for word equations: • Makanin's algorithm, • Plandowski's algorithm, • Jez's algorithm. The approach by Makanin and the approach by Jez can be extended to generate a representation of all solutions of a word equation. In case of Makanin's algorithm the representation is usually an infinite tree. In case of Jez's approach the representation is a finite graph. Until now there was no extension of Plandowski's algorithm to do the same. We fill this gap. We present extension of Plandowski's algorithm which generates a representation of all solutions of a word equation. The representation is a finite graph. This allows to decide in P S P A C E whether a solution set of a word equation is finite. Our approach is generalized to solve in P S P A C E two problems dealing with expressible relations, namely the emptiness of the relation and finiteness of the relation.

TCS Journal 2019 Journal Article

On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note)

• Wojciech Plandowski
• Aleksy Schubert

Denote by SWE the satisfiability problem for word equations. Consider the problem of computability of the maximal exponent of periodicity for word equations MaxExpProblem ( e, k ) in which given positive integer k and a word equation e one is to check whether maximal exponent of periodicity of a solution of a word equation is at least k. We present both a deterministic polynomial time reduction of the MaxExpProblem ( e, k ) problem to the satisfiability problem for word equations and a deterministic polynomial time reduction in the opposite direction. Consequently, if the satisfiability problem is in NP then the other problem is NP-complete. As a simple consequence we get that computation of maximal exponent of periodicity of a solution set for a word equation is in P SWE (SWE is an oracle) and, consequently in PSPACE. Let ϕ be an existential boolean formula built on word equations expressing a relation on words by means of its unknowns. Consider the problem of checking the maximal exponent of periodicity of a component of a relation CMaxExpProblem ( ϕ, k ) in which given positive integer k and a formula ϕ one is to check whether maximal exponent of periodicity of a component of the relation is at least k. We give nondeterministic polynomial time reduction of the described above CMaxExpProblem ( ϕ, k ) problem to the satisfiability problem for word equations and deterministic polynomial time reduction in the other direction. Consequently, if the satisfiability problem is in NP then the other problem is NP-complete. Denote by SAT ( WE ) the satisfiability problem of closed existential formula built on word equations. As a simple consequence of our considerations we get that computation of maximal exponent of periodicity of a component of expressible relation is in P SAT ( WE ) ( SAT ( WE ) is an oracle), and, consequently, in PSPACE. Another consequence of that is that if SWE is in NP, then the computability problem is in P N P. The above results hold also for semigroups with involution. If the expressible relation is defined by a formula using word equations and regular constraints we prove that the problem is PSPACE-complete. The same holds for free semigroups with involution and free groups.

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.

TCS Journal 2009 Journal Article

On systems of word equations over three unknowns with at most six occurrences of one of the unknowns

• Elena Czeizler
• Wojciech Plandowski

In this paper, we investigate the open question, formulated in 1983 by Culik II and Karhumäki, asking whether there exist independent systems of three word equations over three unknowns admitting non-periodic solutions. In particular, we answer negatively the above mentioned question for systems in which one of the unknowns occurs at most six times. That is, we show that such systems admit only periodic solutions or they are not independent.

TCS Journal 2009 Journal Article

Shortest synchronizing strings for Huffman codes

• Marek Tomasz Biskup
• Wojciech Plandowski

Most complete binary prefix codes have a synchronizing string, that is a string that resynchronizes the decoder regardless of its previous state. This work presents an upper bound on the length of the shortest synchronizing string for such codes. Two classes of codes with a long shortest synchronizing string are presented. It is known that finding a synchronizing string for a code is equivalent to finding a synchronizing string of some finite automaton. The Černý conjecture for this class of automata is discussed.

STOC Conference 2006 Conference Paper

An efficient algorithm for solving word equations

• Wojciech Plandowski

We present the first DEXPTIME algorithm which solves word equations i.e. finds a finite representation of all solutions of an equation in a free semigroup. We show how to use our approach to solve two new problems in PSPACE which deal with properties of the solution set of a word equation: deciding finiteness of the solution set, deciding boundness of the set of maximal exponents of periodicity of solutions.

TCS Journal 2005 Journal Article

On the complexity of decidable cases of the commutation problem of languages

• Juhani Karhumäki
• Wojciech Plandowski
• Wojciech Rytter

We investigate the complexity of basic decidable cases of the commutation problem for languages: testing the equality XY = YX for two languages X and Y. We show that it varies from co-NEXPTIME complete through PSPACE complete and co-NP complete to deterministic polynomial time, when Y is an explicitly given finite language and X is given by a CF grammar generating a finite language, a nondeterministic finite automaton (or a regular expression), an acyclic nondeterministic finite automaton or an explicitly given finite language, respectively. Interestingly in most cases the complexity status does not change if instead of explicitly given finite Y we consider general Y of the same type as X. For deterministic finite automata the problem remains open, due to the asymmetry of the catenation.

TCS Journal 2003 Journal Article

A defect theorem for bi-infinite words

• Juhani Karhumäki
• Ján Maňuch
• Wojciech Plandowski

We formulate and prove a defect theorem for bi-infinite words. Let X be a finite set of words over a finite alphabet. If a nonperiodic bi-infinite word w has two X-factorizations, then the combinatorial rank of X is at most card(X)−1, i. e. , there exists a set F such that X⊆F+ with card(F)<card(X). Moreover, in the case when the combinatorial rank of X equals card(X), the number of periodic bi-infinite words which have two different X-factorizations is finite.

MFCS Conference 2002 Conference Paper

On Word Equations in One Variable

• Robert Dabrowski
• Wojciech Plandowski

Abstract For a word equation E of length n in one variable x occurring # x times in E a resolution algorithm of O ( n + # x log n ) time complexity is presented here. This is the best result known and for the equations that feature # x < n /log n it yields time complexity of O ( n ) which is optimal. Additionally, we prove that the set of solutions of one-variable word equations is either of the form F where F is a set of O (log n ) words or of the form F ∪ ( uv ) + u where F is a set of O (log n ) words and u, v are some words such that uv is a primitive word.

TCS Journal 2000 Journal Article

Algorithms for the parallel alternating direction access machine

• Bogdan S. Chlebus
• Artur Czumaj
• Leszek Ga̧sieniec
• Mirosław Kowaluk
• Wojciech Plandowski

We describe a number of algorithms for the model for parallel computation called parallel alternating-direction access machine (padam). This model has the memory modules of the global memory arranged as a two-dimensional array, with each processor assigned to a row and a column, the processors can switch synchronously between row and column access modes. We study the issues of inter-processor communication and of efficient use of memory on the padam, and develop: an optimal routing scheme among memory modules, algorithms enhancing random access of processors to all memory blocks, and general simulations of shared memory machines. Finally, we present optimal algorithms for the problems of selection, merging, and sorting.

TCS Journal 1999 Journal Article

Generalized factorizations of words and their algorithmic properties

• Juhani Karhumäki
• Wojciech Plandowski
• Wojciech Rytter

We formalize the notion of a factorization of a word, a so-called F -factorization, introduced in [7] when solving some open problems on word equations. We show that most of the factorizations considered in the literature fit well into that framework, and in particular that central algorithmic problems, such as the uniqueness or the synchronizability, remain polynomial time solvable for an important and large class of F -factorizations, namely for regular F -factorizations.

STOC Conference 1999 Conference Paper

Satisfiability of Word Equations with Constants is in NEXPTIME

• Wojciech Plandowski

FOCS Conference 1999 Conference Paper

Satisfiability of Word Equations with Constants is in PSPACE

• Wojciech Plandowski

We prove that the satisfiability problem for word equations is in PSPACE. The satisfiability problem for word equations has a simple formulation: find out whether or not an input word equation has a solution. The decidability of the problem was proved by G. S. Makanin (1977). His decision procedure is one of the most complicated algorithms existing in the literature. We propose an alternative algorithm. The full version of the algorithm requires only a proof of the upper bound for index of periodicity of a minimal solution (A. Koscielski and L. Pacholski, see Journal of ACM, vol. 43, no. 4. p. 670-84). Our algorithm is the first one which is proved to work in polynomial space.

MFCS Conference 1998 Conference Paper

On Defect Effect of Bi-Infinite Words

• Juhani Karhumäki
• Ján Manuch
• Wojciech Plandowski

Abstract We prove the following two variants of the defect theorem. Let X be a finite set of words over a finite alphabet. Then if a nonperiodic bi-infinite word w has two X -factorizations, then the combinatorial rank of X is at most card( X ) - 1, i. e. there exists a set F such that \(X \subseteq F^ + \) with card( F ) < card( X ). Further, if card( X )=2 and a bi-infinite word possesses two X -factorizations which are not shift-equivalent, then the primitive roots of the words in X are conjugates. Moreover, in the case card( F )=card( X ), the number of periodic bi-infinite words which have two different X -factorizations is finite and in the two-element case there is at most one such bi-infinite word.

TCS Journal 1996 Journal Article

On the size of independent systems of equations in semigroups

• Juhani Karhumäki
• Wojciech Plandowski

MFCS Conference 1996 Conference Paper

Parallel Alternating-Direction Access Machine

• Bogdan S. Chlebus
• Artur Czumaj
• Leszek Gasieniec
• Miroslaw Kowaluk
• Wojciech Plandowski

Abstract This paper presents a theoretical study of a model of parallel computations called Parallel Alternating-Direction Access Machine ( Padam ). Padam is an abstraction of the multiprocessor computers Adena /adenart and a prototype architecture usc/omp. The main feature of Padam is the organization of access to the global memory: (1) the memory modules are arranged as a 2-dimensional array, (2) each processor is assigned to a row and a column, (3) the processors switch synchronously between row and column access modes, and can access any of the assigned modules in each mode without conflicts. Since the padam processors have such a restricted access to the partially shared memory, developing tools to enhance flexibility of access to the memory is important. The paper concentrates on these issues.

TCS Journal 1995 Journal Article

The zooming method: a recursive approach to time-space efficient string-matching

• Leszek Ga̧sieniec
• Wojciech Plandowski
• Wojciech Rytter

A new approach to time-space efficient string-matching is presented. The method is flexible, its implementation depends whether or not the alphabet is linearly ordered. The only known linear-time constant-space algorithm for string-matching over nonordered alphabets is the Galil-Seiferas algorithm, see Crochemore (1993) and Galil (1983) which are rather complicated. The zooming method gives probably the simplest string-matching algorithm working in constant space and linear time for nonordered alphabets. The novel feature of our algorithm is the application of the searching phase (which is usually simpler than preprocessing) in the preprocessing phase. The preprocessing has a recursive structure similar to selection in linear time, see Aho (1974). For ordered alphabets the preprocessing part is much simpler, its basic component is a simple and well-known algorithm for finding the maximal suffix, see Duval (1983). Hence we demonstrate a new application of this algorithm, see also Crochemore (1991). The idea of the zooming method was applied by Crochemore et al. (1995) to two-dimensional patterns.

STOC Conference 1995 Conference Paper

Work-time-optimal parallel algorithms for string problems

• Artur Czumaj
• Zvi Galil
• Leszek Gasieniec
• Kunsoo Park
• Wojciech Plandowski

MFCS Conference 1994 Conference Paper

On the Size of Independent Systems of Equations in Semigroups

• Juhani Karhumäki
• Wojciech Plandowski