3
$\begingroup$

is there any tree automata model over unranked trees (that is with unbounded number of children for each node), such that:

  1. Checking non-emptiness and universality is decidable in elementary time,
  2. Construction of automata recognizing a projection and the complementation in polynomial size of the input automata, and
  3. Automata is non-deterministic and top-down.

The usual hedge-automata model does not suit me.

$\endgroup$
  • $\begingroup$ Any such model would have to be very weak, since even for finite tree automata (or coBuchi automata over infinite trees) complementation would not be in P (or rather, would be PSPACE hard), as a consequence of this result for word automata. Do you have any reasonable candidates that satisfy property 2? $\endgroup$ – Shaull Mar 4 '18 at 19:41
  • $\begingroup$ Thanks, for your remark. I was thinking about something completely different. I wanted to construct the automata recognizing projection and complementation in polynomial time. $\endgroup$ – Bartosz Bednarczyk Mar 4 '18 at 20:08
  • $\begingroup$ I know that for alternating parity tree automata you can do complementation easily, but to do projection, you need to translate it into non-deterministic one (which costs an exponential blowup). $\endgroup$ – Bartosz Bednarczyk Mar 4 '18 at 20:10
  • 2
    $\begingroup$ My friend and collaborator Andrey and I have been discussing exactly this. If you would like to join our discussion or collaborate, please let me know!! Hope that you have a nice day!! $\endgroup$ – Michael Wehar Mar 5 '18 at 17:23
  • 1
    $\begingroup$ Michael Wehar, I will send you an email soon. $\endgroup$ – Bartosz Bednarczyk Mar 6 '18 at 19:54

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.