SUCCINCT CIRCUIT REPRESENTATIONS AND LEAF LANGUAGE CLASSES ARE BASICALLY THE SAME CONCEPT

Authors
BORCHERT B LOZANO A
Citation
B. Borchert et A. Lozano, SUCCINCT CIRCUIT REPRESENTATIONS AND LEAF LANGUAGE CLASSES ARE BASICALLY THE SAME CONCEPT, Information processing letters, 59(4), 1996, pp. 211-215
Citations number
13
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
59
Issue
4
Year of publication
1996
Pages
211 - 215
Database
ISI
SICI code
0020-0190(1996)59:4<211:SCRALL>2.0.ZU;2-0
Abstract
This note connects two topics of complexity theory: The topic of succi nct circuit representations initiated by Galperin and Wigderson (1983) , and the topic of leaf language classes initiated by Bovet et al. (19 92), It will be shown for any language that its succinct version is po lynomial-time many-one complete for the leaf language class determined by it.