Grammars with Time Functions
The subject of this paper is the study of formal grammars and of formal languages from the viewpoint of time-bounded grammars. The principal results focus on properties similar to those of families of languages defined by time-bounded nondeterministic Turing machines. Chapter 1 contains an overview of the results of this paper and a summary of basic ideas of automata theory and mathematical linguistics used here. In Chapter 2, basic properties of time-bounded grammars and languages generated by time-bounded grammars are investigated. Chapter 3 establishes the positive closure and containment properties of families of languages defined by grammars whose time functions are bounded by bounding functions. Nonclosure, undecidability, and hierarchy results are established in Chapter 4. (Author).
What people are saying - Write a review
We haven't found any reviews in the usual places.
Positive Closure and Containment Properties
Negative Closure Properties and Hierarchy Results
2 other sections not shown
automata theory bounding function closed under intersection closed under inverse computation connected derivation connected grammar Connectivity Theorem context-sensitive language Corollary counter machine Definition derivation in G determined by defining deterministic e-free context-free languages effectively construct end of Phase exact descendant f bounds G families of languages finite formal languages function f Gladkii Gla grammar G Greibach i+1 i+1 IB.I imitate implies integer intersection with regular inverse homomorphism JF(f JFE(f Jt Jt Jt L(GQ l+1 l+1 l+1 Lemma length no greater length-preserving homomorphism Let G linear erasing multitape Turing machine nondeterministic Turing machine nonerasing partial recursive function positive integer prefix Proof proper derivation quasi-realtime languages real-time definable languages recursive sets recursively enumerable sets regular substitution result rules Simulation Theorem ST(f step is connected strongly connected terminal symbols TG(n Type 0 grammar U L(G undecidable unique production sequence w e L(G