Recursive functions of context free languages

MaRDI QIDQ865969zbMATH OpenFDO

Authors Yunmei Dong

Publication date 20 February 2007

Published in Science in China. Series F (Search for Journal in Brave)

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Applications of computability and recursion theory (03D80) Formal languages and automata (68Q45)

Review text

It is intended to establish the recursive function theory on context free languages (CFLs). In this paper, the function class CFRF and its proper subclass CFPRF were defined on CFLs; it is quite straightforward to use them for describing non-numerical algorithms. In fact, they are respectively the partial recursive functions and primitive recursive functions of context free languages. The structure induction method for proving CFPRF function properties was presented. A method for CFL sentence enumeration was given, the minimization operator was defined. Based on CFL sentence enumeration, the minimization operator evaluation method was given. Finally, the design and implementation principles of executable specification languages with the CFRF as theoretical basis were discussed.

Recommendations

• scientific article; zbMATH DE number 2114136
• Regular algebra applied to language problems
• scientific article; zbMATH DE number 1692936
• Multi-type recursive functions
• scientific article; zbMATH DE number 2112161

Cited in

(6)

• scientific article; zbMATH DE number 1692936 (Why is no real title available?)
• Syntactic translations and provably recursive functions
• scientific article; zbMATH DE number 2112161 (Why is no real title available?)
• Multi-type recursive functions
• Theory and Applications of Models of Computation
• Pattern matching compilation of functions defined in context-free languages

This page was built for publication: Recursive functions of context free languages

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