top

A modal perspective on the computational complexity of attribute value grammar

P. Blackburn and E. Spaan. A modal perspective on the computational complexity of attribute value grammar. Journal of Logic, Language and Information, 2:129–169, 1993.

Download: [pdf] 

Abstract:

Attribute value formalisms can be seen as notational variants of propositional (dynamic) modal logic. There are nine different languages of modal logic which in one way or another reflect existing attribute value formalisms. They arise from enriching either a simple polymodal language, a polymodal language with path-equations or a polymodal language with nominals by either the universal modality, the master modality, or no extra operator. The complexity of the satisfiability problem is studied for all these combinations. The following results are proved. If neither the universal modality nor the master modality is present, then the problem is NP-complete; otherwise it is EXPTIME-complete when we have no path-equations, $\Pi\sp 0\sb 1$-complete in the case of path-equations combined with the universal modality, and $\Sigma\sp 1\sb 1$-complete in the remaining case of path-equations in combination with the master modality.

BibTeX: (download)

@ARTICLE{blackburn93,
  author = {P. Blackburn and E. Spaan},
  title = {A modal perspective on the computational complexity of attribute
	value grammar},
  journal = {Journal of Logic, Language and Information},
  year = {1993},
  volume = {2},
  pages = {129--169},
  abstract = {
	Attribute value formalisms can be seen as notational variants of propositional
	(dynamic) modal logic. There are nine different languages of modal
	logic which in one way or another reflect existing attribute value
	formalisms. They arise from enriching either a simple polymodal language,
	a polymodal language with path-equations or a polymodal language
	with nominals by either the universal modality, the master modality,
	or no extra operator. The complexity of the satisfiability problem
	is studied for all these combinations. The following results are
	proved. If neither the universal modality nor the master modality
	is present, then the problem is NP-complete; otherwise it is EXPTIME-complete
	when we have no path-equations, $\Pi\sp 0\sb 1$-complete in the case
	of path-equations combined with the universal modality, and $\Sigma\sp
	1\sb 1$-complete in the remaining case of path-equations in combination
	with the master modality. }
}

Generated by bib2html.pl (written by Patrick Riley ) on Mon Aug 10, 2009 14:52:33