Let Σ be an alphabet. A generalized word equation, GWE for short, is a set of triples and pairs. A triple is in form (p, q, l) where p, q, l are positive integers. A pair is in form (a, i) where a ϵ S and i is a positive integer. A solution of a word equation e is any word w such that, for each triple (p, q, l) in e, w[p..p + l - 1] = w[q..q + l - 1] and, for each pair (a, i) in e, w[i] = a. If there is only one shortest solution w of e, then we say that e defines w. Observe here that if e defines w, then the solution set of e is {ws : s ϵ Σ*}. The triples and pairs of an equation e are called constraints. If an equation e defines a word w, we say that e is a compressed representation of w. Let G be a GWE with m triples and pairs defining a word w. There is an algorithm reconstructing w from G in O(m+ |w|) worst case time [1]. Therefore decompression is optimal. It is not difficult to prove that in simple modifications of GWE generalize LZ77, LZ78 and LZW algorithms. We consider a natural variant of GWE called pGWE and prove that, for a word w, it is a little more efficient and more general than LZ77 for a reversed word wR. Moreover, it can be proved that GWE approach generalizes the bidirectional scheme. We compared GWE with Straight Line Programs (SLP for short) [2, 3] and prove that if SLP for a word w is of length n, then there is a GWE defining w with n constraints. We are not aware of any reasonable simulation in the other direction. We propose a variant of GWE which compresses an input word w in O(|w|L2) worse case time where L is the longest repeating factor in w. This version was tested on files in Canterbury Corpus. It gives better results than gzip on text files and slightly worse on the other files. It is worth mentioning here that gzip is a result of 20 years studies on LZ77 so it is unfair to compare it with our approach. Our current best approach is significantly worse than bzip2 which is based on the Burrows-Wheeler transform.

We describe an intersection of the family of expressible relations and another natural family of relations. This is the first result of this kind existing in the literature. To obtain it we extend a tool for proving nonexpressibility of languages to a tool for proving nonexpressibility of relations.

In Huffman-encoded data a bit error may propagate arbitrarily long. This paper introduces a method for limiting such error propagation to at most L bits, L being a parameter. It is required that the decoder knows the bit number currently being decoded. The method utilizes the inherent tendency of Huffman codes to resynchronize spontaneously and does not introduce any redundancy if such a resynchronization takes place. The method is applied to parallel decoding of Huffman data and is tested on JPEG compression.

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:

We prove that satisfiability problem for word equations is in PSPACE.

Classically, several properties and relations of words, such as “being a power of the same word” can be expressed by using word equations. This paper is devoted to a general study of the expressive power of word equations. As main results we prove theorems which allow us to show that certain properties of words are not expressible as components of solutions of word equations. In particular, “the primitiveness” and “the equal length” are such properties, as well as being “any word over a proper subalphabet”.

We show a simple O(n log n) time algorithm computing the order of repetition in a string. A parallel version of the algorithm works in O(log

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.

Article Satisfiability of word equations with constants is in NEXPTIME Share on Author: Wojciech Plandowski Institute of Informatics, Warsaw University, Banacha 2, 02-097, Warsaw, Poland Institute of Informatics, Warsaw University, Banacha 2, 02-097, Warsaw, PolandView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 721–725https://doi.org/10.1145/301250.301443Published:01 May 1999 32citation300DownloadsMetricsTotal Citations32Total Downloads300Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A parallel algorithm is work-optimal if it uses the srrlallest possible work; a work-optimal algorithm is worktirne-optimal if it also uses the smallest possible time.We design worl{-time-optirnal algorithm for a number of string processing problems on the EREW-PRAM and the hypercuhe, They include string matching and two dimensional pattern matching.No such algorithms have been known before for any of these probl~ms.