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

context-sensitive languageslinear spacespace-efficient computationsstring unificationword equations

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

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

Cites work

• 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
• 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?)
• 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 in nondeterministic linear space
• WORD EQUATIONS OVER GRAPH PRODUCTS

Cited in

(18)

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

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)