961 - Ambiguous or Incomplete Inductive Definitions

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

961 - Ambiguous or Incomplete Inductive Definitions

Post by Jan » Tue Jan 15, 2008 6:37 pm

Tried hard to understand the problem. But the description successfully follows the name (Ambiguous or Incomplete). I am listing some ambiguities or some parts that I couldn't understand:

1. The problem states
Let hB : B -> N be a total function that maps every symbol of B to a positive integer
But check the first sample carefully. 0 is mapped to 0. And 0 is not a positive integer. So, for all regular cases there must be a symbol that is mapped to 0.

2. Check the case

Code: Select all

0 30000
1
1
1
0
( x1 )
Is it valid? Or what is the answer?

3. Again another case

Code: Select all

0 30000
2
6
1
1
2
3
4
5
1
0
( x1 + 1 )
( x1 + 21 )
( x2 + x1 )
( x2 + x3 + x1 )
( x1 + x2 + x3 + x4 )
( x1 + x2 + x3 + x5 * ( x1 * x3 ) * 0 )
What is the output?

4. For some cases the complexity can be N^5? Am I missing something, or the actual problem?

Thanks in advance.

Post Reply

Return to “Volume 9 (900-999)”