Decidable Properties of Monadic Functional Schemas
The work
| Authors | Edward A. Ashcroft; Zohar Manna; Amir Pnueli |
|---|---|
| Editors | |
| Type | article |
| Year | 1973 |
| Citekey | ashcroft1973decidable |
Where it appeared
| Published in | Journal of the ACM |
|---|---|
| Publisher | Association for Computing Machinery |
| Volume | 20 |
| Issue | 3 |
| Pages | 489--499 |
Identifiers
| DOI | 10.1145/321765.321780 |
|---|---|
| OpenAlex | W2028140996 |
Access
| Landing page | https://doi.org/10.1145/321765.321780 |
|---|---|
| Free full text | https://dl.acm.org/doi/pdf/10.1145/321765.321780 |
From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.
Abstract
A class of (monadic) functional schemas which properly includes “Ianov” flowchart schemas is defined. It is shown that the termination, divergence, and freedom problems for functional schemas are decidable. Although it is possible to translate a large class of non-free functional schemas into equivalent free functional schemas, it is shown that in general this cannot be done. It is also shown that the equivalence problem for free functional schemas is decidable. Most of the results are obtained from well-known results in formal languages and automata theory.
How it got here
| How it got here | agent via openalex |
|---|---|
| Added | 2026-10-23 08:24 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Filed under
Cite it as
@article{ashcroft1973decidable,
title = {Decidable Properties of Monadic Functional Schemas},
author = {Edward A. Ashcroft and Zohar Manna and Amir Pnueli},
year = {1973},
journal = {Journal of the ACM},
publisher = {Association for Computing Machinery},
volume = {20},
number = {3},
pages = {489--499},
doi = {10.1145/321765.321780},
}
This record lives at https://refs.drheap.org/ashcroft1973decidable/ and will keep doing so.