Logical embedded push‐down automata in tree‐adjoining grammar parsing

Mark Johnson*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


This paper extends the “parsing as deduction” approach to tree‐adjoining grammars by showing how a TAG recognition problem can be reduced to a Datalog deduction problem, and presents an SLD selection rule that makes the proof search correspond to a top‐down parse using the original grammar. Just as in the DCG extension of context‐free grammars, this approach permits nodes to be labeled with firsl‐order terms (rather than only atomic symbols). Finally the paper discusses implementation matters, and describes how the control rule can be efficiently implemented in Prolog.

Original languageEnglish
Pages (from-to)495-505
Number of pages11
JournalComputational Intelligence
Issue number4
Publication statusPublished - 1994
Externally publishedYes


  • logic programming
  • natural language
  • program transformations


Dive into the research topics of 'Logical embedded push‐down automata in tree‐adjoining grammar parsing'. Together they form a unique fingerprint.

Cite this