Word equations in non-deterministic linear space
DOI10.1016/J.JCSS.2021.08.001zbMATH Open1472.68068OpenAlexW3198190303MaRDI QIDQ2237894FDOQ2237894
Authors: Artur Jeż 
Publication date: 28 October 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7408/
Recommendations
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Cites Work
- Satisfiability of word equations with constants is in NEXPTIME
- Satisfiability of word equations with constants is in PSPACE
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Minimal and complete word unification
- Canonical representatives and equations in hyperbolic groups
- Recompression: a simple and powerful technique for word equations
- Finding all solutions of equations in free groups and monoids with involution
- WORD EQUATIONS OVER GRAPH PRODUCTS
- Complexity of Makanin's algorithm
- Title not available (Why is that?)
- Solutions of word equations over partially commutative structures
- Makanin's algorithm for word equations-two improvements and a generalization
- The existential theory of equations with rational constraints in free groups is PSPACE-complete
- Word equations in nondeterministic linear space
- Solutions to twisted word equations and equations in virtually free groups
- Title not available (Why is that?)
- On PSPACE generation of a solution set of a word equation and its applications
- Deciding context unification
Cited In (17)
- Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibility
- A closer look at the expressive power of logics based on word equations
- Recompression: word equations and beyond
- On PSPACE generation of a solution set of a word equation and its applications
- Equations in words: An algorithmic contribution
- Solving word equations (and other unification problems) by recompression (invited talk)
- Word equations in the context of string solving
- One-Unknown Word Equations and Three-Unknown Constant-Free Word Equations
- On the Solution Sets of Entire Systems of Word Equations
- Non-deterministic linear hypersubstitutions
- Satisfiability of word equations with constants is in NEXPTIME
- The non-parametrizability of the word equation \(xyz=zvx\): a short proof
- Word equations in nondeterministic linear space
- Recompression: technique for word equations and compressed data
- Makanin's algorithm for word equations-two improvements and a generalization
- On the solution sets of three-variable word equations
- Recompression: a simple and powerful technique for word equations
This page was built for publication: Word equations in non-deterministic linear space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2237894)
