Complexity of recognition in intermediate Level languages
- 1 October 1973
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 145-158
- https://doi.org/10.1109/swat.1973.5
Abstract
Complexity of sentence recognition is studied for one-way stack languages, indexed languages, and tree transducer languages. The problem is shown to be polynomial-complete in each case. A class of naturallanguage grammars is formalized and the sentence-recognition problem is shown to be polynomial-hard although the languages are context-sensitive. The proofs give new language-theoretic characterizations of the set of satisfiable propositional formulas and the set of prepositional tautologies.Keywords
This publication has 11 references indexed in Scilit:
- Tree transductions and families of tree languagesPublished by Association for Computing Machinery (ACM) ,1973
- On the generative power of transformational grammarsInformation Sciences, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- The generative capacity of transformational grammars of ginsburg and parteeInformation and Control, 1971
- A Grammatical Characterization of One-Way Nondeterministic Stack LanguagesJournal of the ACM, 1971
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Indexed Grammars—An Extension of Context-Free GrammarsJournal of the ACM, 1968
- Characterizing derivation trees of context-free grammars through a generalization of finite automata theoryJournal of Computer and System Sciences, 1967
- Two Complete Axiom Systems for the Algebra of Regular EventsJournal of the ACM, 1966
- Three models for the description of languageIEEE Transactions on Information Theory, 1956