Nondeterministic Pushdown Automata with Write-Only Output Tapes and Definable Function Classes (<i>Preliminary Report</i>)

概要

論文の詳細を見る
This paper reports preliminary results obtained from a systematic study on the behaviors of multi-valued partial CFL functions, which are computed under various constraints by one-way nondeterministic pushdown automata equipped with additional write-only output tapes. The CFL functions tend to behave quite differently from their corresponding context-free languages. We show several containments and separations among natural classes of CFL functions. We also analyze the computational complexity of languages having properties of selectivity, in which strings (or words) in the languages are selected by appropriate CFL functions. A notion of many-one reducibility introduces relativized CFL functions, which form a hierarchy of CFL function classes. To separate function classes in this hierarchy, we further examine the roles of special oracles that compute multiple values. For a finer analysis, we consider restricted CFL functions having at most k distinct output values and also functions having only values that k CFL functions simultaneously output.
2012-10-26