Decidable properties of monadic recursive schemas with a depth parameter

DOI10.1007/BF00265683MaRDI QIDQ1058305zbMATH OpenOpenAlexFDO

Authors Jakob Gonczarowski

Publication date 1985

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00265683

zbMATH Keywords

depth-of-recursion counterETOL languagesMonadic table counter schemasprogram schemasregular control sequences

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Review text

Monadic table counter schemas (MTCS) are defined as extensions of recursive monadic schemas by incorporating a depth-of-recursion counter. The family of languages generated by free MTCS under Herbrand interpretation is shown to be the family of ETOL languages. It is proven that the halting and divergence problems are decidable for free MTCS and that the freedom problem is decidable. Most of these results are obtained using results on regular control sequences from L system theory.

Recommendations

• The complexity of monadic recursion schemes: Exponential time bounds
• Typed Lambda Calculi and Applications
• scientific article; zbMATH DE number 1670473
• scientific article; zbMATH DE number 4097355
• On the Decidability of the Equivalence Problem for Monadic Recursive Programs

Cited in

(2)

• The complexity of monadic recursion schemes: Exponential time bounds
• Metalinear recursive schemas on marked trees

This page was built for publication: Decidable properties of monadic recursive schemas with a depth parameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1058305)