On the public citation graph

Application of Lempel-Ziv encodings to the solution of word equations

0 signed · 98 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-61258-0_3openalex-snapshot

Randomized efficient algorithms for compressed strings: the finger-print approach

inferredcites →https://doi.org/10.1007/3-540-63165-8_168openalex-snapshot

The expressibility of languages and relations by word equations

inferredcites →https://doi.org/10.1007/978-3-642-59136-5_6openalex-snapshot

Combinatorics of Words

inferredcites →https://doi.org/10.1007/bfb0049431openalex-snapshot

Testing equivalence of morphisms on context-free languages

inferredcites →https://doi.org/10.1007/bfb0055097openalex-snapshot

Application of Lempel-Ziv encodings to the solution of word equations

inferredcites →https://doi.org/10.1016/0022-0000(80)90041-0openalex-snapshot

Finding patterns common to a set of strings

inferredcites →https://doi.org/10.1070/sm1977v032n02abeh002376openalex-snapshot

THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP

inferredcites →https://doi.org/10.1109/tit.1976.1055501openalex-snapshot

On the Complexity of Finite Sequences

inferredcites →https://doi.org/10.1145/225058.225288openalex-snapshot

String matching in Lempel-Ziv compressed strings

inferredcites →https://doi.org/10.1145/234533.234543openalex-snapshot

Complexity of Makanin's algorithm

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/10719839_38openalex-snapshot

Equations in Free Semigroups with Anti-involution and Their Relation to Equations in Free Groups

inferred← citeshttps://doi.org/10.1007/11532231_11openalex-snapshot

Well-Nested Context Unification

inferred← citeshttps://doi.org/10.1007/3-540-44693-1_15openalex-snapshot

The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE—Complete

inferred← citeshttps://doi.org/10.1007/3-540-45005-x_5openalex-snapshot

A Remark about Quadratic Trace Equations

inferred← citeshttps://doi.org/10.1007/3-540-45655-4_40openalex-snapshot

Algorithms for Normal Curves and Surfaces

inferred← citeshttps://doi.org/10.1007/3-540-45687-2_17openalex-snapshot

On Word Equations in One Variable

inferred← citeshttps://doi.org/10.1007/3-540-47849-3_3openalex-snapshot

Algorithms on Compressed Strings and Arrays

inferred← citeshttps://doi.org/10.1007/3-540-48340-3_5openalex-snapshot

Efficiency of Fast Parallel Pattern Searching in Highly Compressed Texts

inferred← citeshttps://doi.org/10.1007/3-540-49116-3_20openalex-snapshot

On Quadratic Word Equations

inferred← citeshttps://doi.org/10.1007/3-540-49519-3_4openalex-snapshot

Solving Bit-Vector Equations

inferred← citeshttps://doi.org/10.1007/978-1-4939-0748-9openalex-snapshot

The Compressed Word Problem for Groups

inferred← citeshttps://doi.org/10.1007/978-1-4939-0748-9_7openalex-snapshot

Outlook

inferred← citeshttps://doi.org/10.1007/978-3-030-30806-3_8openalex-snapshot

On Solving Word Equations Using SAT

inferred← citeshttps://doi.org/10.1007/978-3-030-40608-0_4openalex-snapshot

Recompression: Technique for Word Equations and Compressed Data

inferred← citeshttps://doi.org/10.1007/978-3-031-05578-2_2openalex-snapshot

Word Equations in the Context of String Solving

inferred← citeshttps://doi.org/10.1007/978-3-031-15077-7_8openalex-snapshot

Solving String Theories Involving Regular Membership Predicates Using SAT

inferred← citeshttps://doi.org/10.1007/978-3-031-72200-4_21openalex-snapshot

Computing String Covers in Sublinear Time

inferred← citeshttps://doi.org/10.1007/978-3-031-78116-2_2openalex-snapshot

SMTQuery: Analysing SMT-LIB String Benchmarks

inferred← citeshttps://doi.org/10.1007/978-3-032-09524-4_4openalex-snapshot

Word Equations with Length Constraints via Weak Arithmetics and Matrix Reachability Problems

inferred← citeshttps://doi.org/10.1007/978-3-319-06686-8_1openalex-snapshot

Finding All Solutions of Equations in Free Groups and Monoids with Involution

inferred← citeshttps://doi.org/10.1007/978-3-319-23021-4_2openalex-snapshot

More Than 1700 Years of Word Equations

inferred← citeshttps://doi.org/10.1007/978-3-540-25945-9_15openalex-snapshot

An Evolutionary Algorithm for Solving Word Equation Systems

inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_36openalex-snapshot

Solving Two-Variable Word Equations

inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_5openalex-snapshot

Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input

inferred← citeshttps://doi.org/10.1007/978-3-540-28645-5_9openalex-snapshot

Word Equation Systems: The Heuristic Approach

inferred← citeshttps://doi.org/10.1007/978-3-540-76631-5_30openalex-snapshot

A Word Equation Solver Based on Levensthein Distance

inferred← citeshttps://doi.org/10.1007/978-3-540-77505-8_2openalex-snapshot

A Symbolic Intruder Model for Hash-Collision Attacks

inferred← citeshttps://doi.org/10.1007/978-3-540-78499-9_19openalex-snapshot

Systems of Equations Satisfied in All Commutative Finite Semigroups

inferred← citeshttps://doi.org/10.1007/978-3-642-02737-6_36openalex-snapshot

On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations

inferred← citeshttps://doi.org/10.1007/978-3-642-03351-3_23openalex-snapshot

Compressed Word Problems in HNN-Extensions and Amalgamated Products

inferred← citeshttps://doi.org/10.1007/978-3-642-14455-4_21openalex-snapshot

Compressed Conjugacy and the Word Problem for Outer Automorphism Groups of Graph Groups

inferred← citeshttps://doi.org/10.1007/978-3-642-38771-5_2openalex-snapshot

Recompression: Word Equations and Beyond

inferred← citeshttps://doi.org/10.1007/978-3-642-39212-2_30openalex-snapshot

One-Variable Word Equations in Linear Time

inferred← citeshttps://doi.org/10.1007/978-3-642-60207-8_23openalex-snapshot

Complexity of Language Recognition Problems for Compressed Words

inferred← citeshttps://doi.org/10.1007/978-3-642-60207-8_28openalex-snapshot

Quadratic Word Equations

inferred← citeshttps://doi.org/10.1007/978-3-662-43951-7_21openalex-snapshot

Context Unification is in PSPACE

inferred← citeshttps://doi.org/10.1007/978-3-662-47666-6_11openalex-snapshot

Solution Sets for Equations over Free Groups are EDT0L Languages

inferred← citeshttps://doi.org/10.1007/s00224-010-9295-2openalex-snapshot

Compressed Word Problems in HNN-extensions and Amalgamated Products

inferred← citeshttps://doi.org/10.1007/s00224-013-9443-6openalex-snapshot

The Complexity of Compressed Membership Problems for Finite Automata

inferred← citeshttps://doi.org/10.1007/s00224-020-10013-wopenalex-snapshot

On the Complexity of the Smallest Grammar Problem over Fixed Alphabets

inferred← citeshttps://doi.org/10.1007/s00224-021-10058-5openalex-snapshot

On the structure of solution-sets to regular word equations

inferred← citeshttps://doi.org/10.1007/s00224-025-10258-3openalex-snapshot

Computing String Covers in Sublinear Time

inferred← citeshttps://doi.org/10.1007/s00453-009-9375-3openalex-snapshot

On Word Equations in One Variable

inferred← citeshttps://doi.org/10.1007/s00453-014-9931-3openalex-snapshot

One-Variable Word Equations in Linear Time

inferred← citeshttps://doi.org/10.1007/s00453-022-01092-xopenalex-snapshot

Near-Optimal Quantum Algorithms for String Problems

inferred← citeshttps://doi.org/10.1007/s00454-013-9515-zopenalex-snapshot

Tracing Compressed Curves in Triangulated Surfaces

inferred← citeshttps://doi.org/10.1007/s10601-025-09379-wopenalex-snapshot

Word equations in synergy with regular constraints (extended version)

inferred← citeshttps://doi.org/10.1007/s11390-025-4684-9openalex-snapshot

A Separation Logic for Sequences in Block-Based Cloud Storage Systems and Its Decidability

inferred← citeshttps://doi.org/10.1016/j.ic.2005.04.002openalex-snapshot

The existential theory of equations with rational constraints in free groups is PSPACE-complete

inferred← citeshttps://doi.org/10.1016/j.jcss.2021.08.001openalex-snapshot

Word equations in non-deterministic linear space

inferred← citeshttps://doi.org/10.1016/j.ress.2020.107011openalex-snapshot

Algorithms for Bayesian network modeling and reliability inference of complex multistate systems: Part I – Independent systems

inferred← citeshttps://doi.org/10.1016/j.tcs.2018.10.023openalex-snapshot

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

inferred← citeshttps://doi.org/10.1016/s0022-0000(03)00045-xopenalex-snapshot

Recognizing string graphs in NP

inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00642-4openalex-snapshot

Equations in free semigroups with involution and their relation to equations in free groups

inferred← citeshttps://doi.org/10.1109/5.892712openalex-snapshot

Compressed and fully compressed pattern matching in one and two dimensions

inferred← citeshttps://doi.org/10.1109/dcc.1999.755681openalex-snapshot

Almost-optimal fully LZW-compressed pattern matching

inferred← citeshttps://doi.org/10.1109/focs.2017.26openalex-snapshot

Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve

inferred← citeshttps://doi.org/10.1109/sfcs.1998.743434openalex-snapshot

Satisfiability of word equations with constants is in exponential space

inferred← citeshttps://doi.org/10.1109/sffcs.1999.814622openalex-snapshot

Satisfiability of word equations with constants is in PSPACE

inferred← citeshttps://doi.org/10.1137/1.9781611973730.36openalex-snapshot

Internal Pattern Matching Queries in a Text and Applications

inferred← citeshttps://doi.org/10.1137/1.9781611977073.109openalex-snapshot

Near-Optimal Quantum Algorithms for String Problems

inferred← citeshttps://doi.org/10.1142/s0218196712400073openalex-snapshot

COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS

inferred← citeshttps://doi.org/10.1142/s0218196715400056openalex-snapshot

SLP compression for solutions of equations with constraints in free and hyperbolic groups

inferred← citeshttps://doi.org/10.1142/s0218196720500198openalex-snapshot

Solutions to twisted word equations and equations in virtually free groups

inferred← citeshttps://doi.org/10.1142/s0218196726500402openalex-snapshot

Solutions of word equations over partially commutative structures

inferred← citeshttps://doi.org/10.1145/1132516.1132584openalex-snapshot

An efficient algorithm for solving word equations

inferred← citeshttps://doi.org/10.1145/2261250.2261270openalex-snapshot

Tracing compressed curves in triangulated surfaces

inferred← citeshttps://doi.org/10.1145/2743014openalex-snapshot

Recompression

inferred← citeshttps://doi.org/10.1145/301250.301443openalex-snapshot

Satisfiability of word equations with constants is in NEXPTIME

inferred← citeshttps://doi.org/10.1145/335305.335308openalex-snapshot

Satisfiability of equations in free groups is in PSPACE

inferred← citeshttps://doi.org/10.1145/3356904openalex-snapshot

Deciding Context Unification

inferred← citeshttps://doi.org/10.1145/3373394.3373396openalex-snapshot

Strings at MOSCA

inferred← citeshttps://doi.org/10.1145/3517804.3524159openalex-snapshot

Data Path Queries over Embedded Graph Databases

inferred← citeshttps://doi.org/10.1145/3672395openalex-snapshot

Quantum Speed-Ups for String Synchronizing Sets, Longest Common Substring, and k -mismatch Matching

inferred← citeshttps://doi.org/10.1145/509907.509910openalex-snapshot

Recognizing string graphs in NP

inferred← citeshttps://doi.org/10.1145/990308.990312openalex-snapshot

Satisfiability of word equations with constants is in PSPACE

inferred← citeshttps://doi.org/10.1515/gcc-2012-0016openalex-snapshot

Algorithmics on SLP-compressed strings: A survey

inferred← citeshttps://doi.org/10.17760/d20383647openalex-snapshot

Typed programming language : the semantics of rank polymorphism

inferred← citeshttps://doi.org/10.21941/kcss/2022/1openalex-snapshot

Light On String Solving

inferred← citeshttps://doi.org/10.4230/lipics.cpm.2021.8openalex-snapshot

Weighted Ancestors in Suffix Trees Revisited

inferred← citeshttps://doi.org/10.4230/lipics.stacs.2012.136openalex-snapshot

Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)

inferred← citeshttps://doi.org/10.48550/arxiv.0811.3303openalex-snapshot

Compressed word problems in HNN-extensions and amalgamated products

inferred← citeshttps://doi.org/10.48550/arxiv.1106.1000openalex-snapshot

Compressed word problems for inverse monoids

inferred← citeshttps://doi.org/10.48550/arxiv.1502.03426openalex-snapshot

Solution sets for equations over free groups are EDT0L languages -- ICALP 2015 version

inferred← citeshttps://doi.org/10.48550/arxiv.1702.00736openalex-snapshot

Word equations in linear space

inferred← citeshttps://doi.org/10.48550/arxiv.2110.09696openalex-snapshot

Near-Optimal Quantum Algorithms for String Problems

inferred← citeshttps://doi.org/10.7146/brics.v6i18.20075openalex-snapshot

Solving Bit-Vector Equations of Fixed and Non-Fixed Size

showing the first 87 of 88 · page through all 88

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.