Polynomial-Time Inference of Paralleled Even Monogenic Pure Context-Free Languages
Summary :
We introduce a subclass of context-free languages, called pure context-free (PCF) languages, which is generated by context-free grammars with only one type of symbol (i. e. , terminals and nonterminals are not distinguished), and consider the problem of identifying paralleled even monogenic pure context-free (pem-PCF) languages, PCF languages with restricted and enhanced features, from positive data only. In this paper we show that the ploblem of identifying the class of pem-PCF languages is reduced to the ploblem of identifying the class of monogenic PCF (mono-PCF), by decomposing each string of pem-PCF languages. Then, with its result, we show that the class of pem-PCF languages is polynomial time identifiable in the limit from positive data. Further, we refer to properties of its identification algorithm.
- Publication
- IEICE TRANSACTIONS on Information Vol.E81-D No.3 pp.261-270
- Publication Date
- 1998/03/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- Algorithm and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Noriyuki TANIDA, "Polynomial-Time Inference of Paralleled Even Monogenic Pure Context-Free Languages" in IEICE TRANSACTIONS on Information,
vol. E81-D, no. 3, pp. 261-270, March 1998, doi: .
Abstract: We introduce a subclass of context-free languages, called pure context-free (PCF) languages, which is generated by context-free grammars with only one type of symbol (i. e. , terminals and nonterminals are not distinguished), and consider the problem of identifying paralleled even monogenic pure context-free (pem-PCF) languages, PCF languages with restricted and enhanced features, from positive data only. In this paper we show that the ploblem of identifying the class of pem-PCF languages is reduced to the ploblem of identifying the class of monogenic PCF (mono-PCF), by decomposing each string of pem-PCF languages. Then, with its result, we show that the class of pem-PCF languages is polynomial time identifiable in the limit from positive data. Further, we refer to properties of its identification algorithm.
URL: https://global.ieice.org/en_transactions/information/10.1587/e81-d_3_261/_p
Copy
@ARTICLE{e81-d_3_261,
author={Noriyuki TANIDA, },
journal={IEICE TRANSACTIONS on Information},
title={Polynomial-Time Inference of Paralleled Even Monogenic Pure Context-Free Languages},
year={1998},
volume={E81-D},
number={3},
pages={261-270},
abstract={We introduce a subclass of context-free languages, called pure context-free (PCF) languages, which is generated by context-free grammars with only one type of symbol (i. e. , terminals and nonterminals are not distinguished), and consider the problem of identifying paralleled even monogenic pure context-free (pem-PCF) languages, PCF languages with restricted and enhanced features, from positive data only. In this paper we show that the ploblem of identifying the class of pem-PCF languages is reduced to the ploblem of identifying the class of monogenic PCF (mono-PCF), by decomposing each string of pem-PCF languages. Then, with its result, we show that the class of pem-PCF languages is polynomial time identifiable in the limit from positive data. Further, we refer to properties of its identification algorithm.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - Polynomial-Time Inference of Paralleled Even Monogenic Pure Context-Free Languages
T2 - IEICE TRANSACTIONS on Information
SP - 261
EP - 270
AU - Noriyuki TANIDA
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E81-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 1998
AB - We introduce a subclass of context-free languages, called pure context-free (PCF) languages, which is generated by context-free grammars with only one type of symbol (i. e. , terminals and nonterminals are not distinguished), and consider the problem of identifying paralleled even monogenic pure context-free (pem-PCF) languages, PCF languages with restricted and enhanced features, from positive data only. In this paper we show that the ploblem of identifying the class of pem-PCF languages is reduced to the ploblem of identifying the class of monogenic PCF (mono-PCF), by decomposing each string of pem-PCF languages. Then, with its result, we show that the class of pem-PCF languages is polynomial time identifiable in the limit from positive data. Further, we refer to properties of its identification algorithm.
ER -
English
