patternMinor
Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?
Viewed 0 times
polynomialtimelanguagealgorithmdowndeterminetherewhetheremptible
Problem
Definitions:
An up down language is a language whose alphabet is a set of pairs, but not characters, of two characters, where the one character in the pair is the opposite of the other character in the pair.
Each word in the language is concatenation of some characters from the alphabet given in the pairs of the alphabet set.
An up down language is emptible if and only if you can empty it, so it becomes Φ phi, without getting an empty word, which is marked as ε epsilon, before by only doing the "reduce" action only.
The "reduce" action is an action which removes a pair from the alphabet and then removes all words from the language that own/contain one character in the removed pair and also removes the other character in the removed pair from all words that were left/remaining in the language (after the first removal) that own/contain the other character in the removed pair. As a result the language becomes a set with fewer/lesser shorter words. This way it is possible to empty the language by repeating this action, i.e. the "reduce" action only, but it is also possible to get an empty word, i.e. epsilon ε.
Summary/In conclusion:
When given non empty up down language that doesn't own/contain the empty word ε epsilon, your objectives are/goal is:
Examples:
The following up down language is emptible:
L={abc,bxd,ye} where Σ={(a,z),(b,y),(c,x),(d,w),(e,v)}
Because
Reduce(b,L)={e} where Σ={(e,v)} Note that the words that owned/contained the letter 'b' were removed from the language and the letter 'y' was removed as well, because 'b' was paired with 'y', so the word "ye" was shorten to "e"
and
Reduce(e,{e})=Φ
I could get Φ without getting ε so the above up down language is indeed emptible
But the following up down language is not emptible:
L={ab,ay,zc,zx
An up down language is a language whose alphabet is a set of pairs, but not characters, of two characters, where the one character in the pair is the opposite of the other character in the pair.
Each word in the language is concatenation of some characters from the alphabet given in the pairs of the alphabet set.
An up down language is emptible if and only if you can empty it, so it becomes Φ phi, without getting an empty word, which is marked as ε epsilon, before by only doing the "reduce" action only.
The "reduce" action is an action which removes a pair from the alphabet and then removes all words from the language that own/contain one character in the removed pair and also removes the other character in the removed pair from all words that were left/remaining in the language (after the first removal) that own/contain the other character in the removed pair. As a result the language becomes a set with fewer/lesser shorter words. This way it is possible to empty the language by repeating this action, i.e. the "reduce" action only, but it is also possible to get an empty word, i.e. epsilon ε.
Summary/In conclusion:
When given non empty up down language that doesn't own/contain the empty word ε epsilon, your objectives are/goal is:
- Get the empty language Φ phi, which is a must.
- Do not get the empty word ε epsilon before, which is forbidden.
- You can only do the "reduce" action as defined above to achieve the first objective 1.
Examples:
The following up down language is emptible:
L={abc,bxd,ye} where Σ={(a,z),(b,y),(c,x),(d,w),(e,v)}
Because
Reduce(b,L)={e} where Σ={(e,v)} Note that the words that owned/contained the letter 'b' were removed from the language and the letter 'y' was removed as well, because 'b' was paired with 'y', so the word "ye" was shorten to "e"
and
Reduce(e,{e})=Φ
I could get Φ without getting ε so the above up down language is indeed emptible
But the following up down language is not emptible:
L={ab,ay,zc,zx
Solution
Reduction from 3-SAT:
a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word.
e.g.
Selecting a character in your problem means setting that literal to true in the 3-SAT instance. The corresponding clauses are removed (they are satisfied) and the remaining clauses that contain the negation of that character/literal have that literal removed, as those clauses need to be satisfied with one of the remaining literals.
It is NP-hard.
a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word.
e.g.
- 3 SAT: (a,b,-c) && (-b,c) =>
- pairs: (a,-a), (b,-b), (c,-c).
- words: (a,b,-c), (-b,c)
Selecting a character in your problem means setting that literal to true in the 3-SAT instance. The corresponding clauses are removed (they are satisfied) and the remaining clauses that contain the negation of that character/literal have that literal removed, as those clauses need to be satisfied with one of the remaining literals.
It is NP-hard.
Context
StackExchange Computer Science Q#76931, answer score: 7
Revisions (0)
No revisions yet.