Satisfiability of Word Equations with Constants is in PSPACE.
Wojciech PlandowskiPublished in: FOCS (1999)
Keyphrases
- decision procedures
- satisfiability problem
- co occurrence
- propositional logic
- pspace complete
- terminological reasoning
- word recognition
- np complete
- mathematical model
- mazurkiewicz traces
- computational complexity
- n gram
- temporal logic
- numerical solution
- linear systems
- satisfiability testing
- polynomial equations
- related words
- computational properties
- sat problem
- natural language text
- search engine
- noun phrases
- word sense disambiguation
- knowledge base