283
edits
Pipe-calculus: Difference between revisions
→Variants
KalmanKeri (talk | contribs) No edit summary |
KalmanKeri (talk | contribs) |
||
| Line 26: | Line 26: | ||
The most simple variant of the calculus that is lacking variables and scoped constructs is called '''zero-order'''. | The most simple variant of the calculus that is lacking variables and scoped constructs is called '''zero-order'''. | ||
Somewhat surprisingly, even the zero-order calculus has a limited computational power. | Somewhat surprisingly, even the zero-order calculus has a limited computational power. | ||
In '''higher-order''' | In the '''higher-order''' calculus there are lexically scoped variables that can bind arbitrary terms. Intermediate variants can be constructed by extending the basic calculus with recursion and with a stack. | ||
When used as recognizers, extended variants of the calculus can generally recognize more expressive formal languages. | When used as recognizers, extended variants of the calculus can generally recognize more expressive formal languages. | ||