Hi all.
I have the following data type:
data Expr =
Literal Integer
| Add Expr Expr -- x + y
| Multipy Expr Expr -- x*y
| Power Expr Expr -- x^y
It represents an expression, which can consist of signed integer
literals (arbitrary size), and operators:
addition, multiplication, exponentiation. Semantically, this
expression may denote a complex number. If
an exponentiation is ambiguous, let it represent a complex number with
a minimal non-negative argument.
For instance, Power (Literal (-1)) (Power (Literal 2) (Literal (-1)))
represents I (the imaginary unit), not (-I).
One can see, that it is possible to encode all rational numbers and
some algebraic numbers in this way.
I need to write an algorithm, which accepts an expression (a value of
type Expr) and produces one of the following results:
1) the expression is invalid, in other words, it contains a
subexpression of the form p^q, where p=0 and Re(q)<=0
(for instance, the expression Power (Literal 0) (Literal 0) is
invalid)
2) the expression equals to zero (for instance, the expression Add
(Literal 1) (Literal (-1)) equals to zero)
3) the expression is not equal to zero (for instance, the expression
Literal 2 is not equal to zero)
Is this task decidable?
Thanks,
nikov
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
