Control sets on grammars

DOI10.1007/BF01692513zbMath0157.33604MaRDI QIDQ5539750

Edwin H. Spanier, Seymour Ginsburg

Publication date: 1968

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

recursively enumerable setphrase structure grammarcontext freecontext tree language

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On certain formal properties of grammars
• Note on the boolean properties of context free languages
• A note on asymmetry in phrase structure grammars
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Bounded Algol-Like Languages
• Mappings which preserve context sensitive languages
• Two-way languages
• Three models for the description of language
• One-way stack automata
• Preservation of languages by transducers
• Studies in abstract families of languages

Related Items (46)

Error tolerance for the recognition of faulty strings in a regulated grammar using fuzzy sets ⋮ Some formal results about stratificational grammars and their relevance to linguistics ⋮ One-Sided Random Context Grammars with Leftmost Derivations ⋮ Grammars, derivation modes and properties of indexed and type-0 languages ⋮ The OI-hierarchy is closed under control ⋮ Grammatical inference for even linear languages based on control sets ⋮ Pumping lemmas for the control language hierarchy ⋮ Images of AFL under certain families of homomorphisms ⋮ Accepting grammars with regulation ⋮ Computing by observing: simple systems and simple observers ⋮ HYBRID EXTENDED FINITE AUTOMATA ⋮ Monotonically controlling right linear grammars with unknown behaviors to output a target string ⋮ Weighted iterated linear control ⋮ A Myhill-Nerode theorem for finite state matrix automata and finite matrix languages ⋮ Iterated linear control and iterated one-turn pushdowns ⋮ Reducing control alphabet size for the control of right linear grammars with unknown behaviors ⋮ Storage products and linear control of derivations ⋮ A generalization of leftmost derivations ⋮ Two-way A-transducers and AFL ⋮ Size, index, and context-sensitivity of controlled partition grammars ⋮ Interactive languages ⋮ Uniformly erasable AFL ⋮ Notes on canonical label languages ⋮ Characterization theorems on abstract families of transducers ⋮ Basic tree transducers ⋮ Degree-languages: A new concept of acceptance ⋮ Control sets on context-free grammar forms ⋮ Theory of \(\omega\)-languages. II: A study of various models of \(\omega\)- type generation and recognition ⋮ One way finite visit automata ⋮ Remarks on context-free grammars with subregular control languages ⋮ Fast recognition of context-sensitive structures ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ Derivation-bounded languages ⋮ A hierarchy between context-free and context-sensitive languages ⋮ Abstract families of processors ⋮ Control sets on grammars using depth-first derivations ⋮ DECISION PROBLEMS ON PATH-CONTROLLED GRAMMARS ⋮ General formulation of formal grammars ⋮ AFL with the semilinear property ⋮ Some concepts for languages more powerful than context-free ⋮ On input-revolving deterministic and nondeterministic finite automata ⋮ Normal forms for context-sensitive grammars ⋮ Theory of formal grammars ⋮ Linear indexed languages ⋮ Even linear simple matrix languages: formal language properties and grammatical inference. ⋮ Fuzzy state grammar and fuzzy deep pushdown automaton

This page was built for publication: Control sets on grammars