Name
Abstract | ||
|---|---|---|
We exhibit a sequence Sn (n � 0) of while program schemes, i. e., while programs without interpretation, with the prop- erty that the while nesting depth of Sn is n, and prove that any while program scheme which is scheme equivalent to Sn, i. e., equivalent for all interpretations over arbitrary domains, has while nesting depth at least n. This shows that the while nesting depth imposes a strict hier- archy (the while hierarchy) when programs are compared with respect to scheme equivalence and contrasts with Kleene's classical result that every program is equivalent to a program of while nesting depth 1 (when in- terpreted over a fixed domain with arithmetic on non-negative integers). Our proof is based on results from formal language theory; in particular, we make use of the notion of star height of regular languages. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/BFb0053540 | FoSSaCS |
Keywords | Field | DocType |
program schemes,formal language,regular language | Integer,Discrete mathematics,Combinatorics,Formal language,Star height,Contrast (statistics),Equivalence (measure theory),Regular language,Hierarchy,Mathematics | Conference |
Volume | ISSN | ISBN |
1378 | 0302-9743 | 3-540-64300-1 |
Citations | PageRank | References |
1 | 0.35 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Can Adam Albayrak | 1 | 4 | 3.17 |
| Thomas Noll | 2 | 23 | 6.12 |