Word equations in non-deterministic linear space

DOI10.1016/J.JCSS.2021.08.001MaRDI QIDQ2237894zbMATH OpenOpenAlexFDO

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/

zbMATH Keywords

linear spacestring unificationword equationscontext-sensitive languagesspace-efficient computations

Mathematics Subject Classification ID

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)

Recommendations

• Word equations in nondeterministic linear space
• Recompression: word equations and beyond
• Recompression: a simple and powerful technique for word equations
• scientific article
• Satisfiability of word equations with constants is in NEXPTIME

Cites work

• scientific article; zbMATH DE number 3577484 (Why is no real title available?)
• scientific article; zbMATH DE number 1223734 (Why is no real title available?)
• scientific article; zbMATH DE number 1114346 (Why is no real title available?)
• scientific article; zbMATH DE number 3805807 (Why is no real title available?)
• scientific article; zbMATH DE number 7087296 (Why is no real title available?)
• Canonical representatives and equations in hyperbolic groups
• Complexity of Makanin's algorithm
• Deciding context unification
• Finding all solutions of equations in free groups and monoids with involution
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Makanin's algorithm for word equations-two improvements and a generalization
• Minimal and complete word unification
• On PSPACE generation of a solution set of a word equation and its applications
• Recompression: a simple and powerful technique for word equations
• Satisfiability of word equations with constants is in NEXPTIME
• Satisfiability of word equations with constants is in PSPACE
• Solutions of word equations over partially commutative structures
• Solutions to twisted word equations and equations in virtually free groups
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• WORD EQUATIONS OVER GRAPH PRODUCTS
• Word equations in nondeterministic linear space

Cited in

(17)

• Word equations in nondeterministic linear space
• Word equations in the context of string solving
• Recompression: word equations and beyond
• Recompression: technique for word equations and compressed data
• A closer look at the expressive power of logics based on word equations
• One-Unknown Word Equations and Three-Unknown Constant-Free Word Equations
• Recompression: a simple and powerful technique for word equations
• On PSPACE generation of a solution set of a word equation and its applications
• Equations in words: An algorithmic contribution
• The non-parametrizability of the word equation \(xyz=zvx\): a short proof
• Non-deterministic linear hypersubstitutions
• On the Solution Sets of Entire Systems of Word Equations
• Solving word equations (and other unification problems) by recompression (invited talk)
• Makanin's algorithm for word equations-two improvements and a generalization
• Satisfiability of word equations with constants is in NEXPTIME
• Quadratic word equations with length constraints, counter systems, and Presburger arithmetic with divisibility
• On the solution sets of three-variable 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)