Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Assume we have a simple programming language with while, if, := (assignment), input v and output v. Where input v reads an arbitrary value into variable v and output v outputs the value in v. For simplicity we use boolean values only. Further the program can only use $k$ variables but is of any finite length, and the program should not terminate.

The input-output behavior of any program can be captured in an infinite tree, where the edges are labeled by input values and the nodes with output values.

If we consider all possible programs, is the set of all input-output trees $\omega$-regular?

My thoughts: The programs are deterministic, only the input is not. Thus complex languages like ${(0^n1^n)^\omega}$, are not possible unless the inputs help us. On the other hand the length of a program is unspecified, which makes complex computations possible if the program is only long enough.

Do you have pointers where I should research? Any hints and comments are welcome, thanks.

EDIT: I guess the language is not regular. Though its not a prove the following is a convincing argument I think. Actually ${(0^n1^n)^\omega}$ is a possible output for a program. The program has $n$ output 0 statements, followed by $n$ output 1 and all that in a while loop. However $0^110^210^310^4\dots$ is not possible, for any program of finite length with finite memory. For some $\omega$-automaton to differentiate these two cases and all similar cases is too much, I think

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.