<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Single Tree Grammars11Research of Weiping Shi was supported in part by the Semiconductor Research Corporation under contract 88-DP-109 and in part by the National Science Foundation under grant CCR-8710730. Research of Shai Simonson was supported by the National Science Foundation under grant CCR-8710730.

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Conference object , Book 01 Jan 1992 English Publisher:Elsevier BV

Authors: Sheila A. Greibach; Shai Simonson; Weiping Shi;

doi: 10.1016/b978-0-12-708240-0.50008-3 , 10.13140/2.1.4034.9124

Single Tree Grammars11Research of Weiping Shi was supported in part by the Semiconductor Research Corporation under contract 88-DP-109 and in part by the National Science Foundation under grant CCR-8710730. Research of Shai Simonson was supported by the National Science Foundation under grant CCR-8710730.

- Summary
- Metrics

Abstract

Abstract A context-free grammar is a single-tree grammar (STG) if every nonterminal symbol has at most one production rule whose right hand side contains nonterminal symbols. Various properties of this class of grammars are studied. Although most properties of STG's are undecidable, every linear STG generates a bounded language and a deterministic context-free language, so most properties of linear STG's are decidable. Finally, we show that STG grammars have natural applications for logic database query languages.

Related Organizations

University of California, Los Angeles
United States
University of Illinois at Urbana Champaign
United States
Stonehill College
United States
Department of Physics, Mathematics and Informatics
Belarus
University of Chicago
United States

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	4
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average