1988 · 49 citations · 8 references
ComputingComputer ScienceMathematicsAlgorithmsComputational LinguisticsFormal MethodsAbstract Syntax TreesFormal Language FoundationsFormal LanguagesLanguage ModelingRecursion TheorySyntax AnalysisComputational Complexity Of LanguagesComputational NotationGrammar FormalismsLanguage Generating SystemsPolynomial Time ComplexityPolynomial-time Algorithms
We investigate the weak expressive power of a notation using first-order logic, augmented with a facility for recursion, to give linguistic descriptions. The notation is precise and easy to read, using ordinary conventions of logic. Two versions of the notation are presented. One, called CLFP, speaks about strings and concatenation, and generates the class EXPTIME of languages accepted by Turing machines in time 2cn for some c > 0. The other, called ILFP, speaks about integer positions in strings, and generates the class PTIME of languages recognizable in polynomial time. An application is given, showing how to code Head Grammars in ILFP, showing why these grammars generate only polynomial time languages.
8
Generalized Phrase Structure Grammar.
Scott Soames, Gerald Gazdar, Ewan Klein et al. · The Philosophical Review · 1989 · 1.8K citations
The complexity of relational query languages (Extended Abstract)
Moshe Y. Vardi · 1982 · 1.2K citations
Computing, Computer Science, Algebra +16
Relational queries computable in polynomial time
Neil Immerman · Information and Control · 1986 · 648 citations