Polynomial time learner for inferring subclasses of internal contextual grammars with local maximum selectors
- Title
- Polynomial time learner for inferring subclasses of internal contextual grammars with local maximum selectors
- Creator
- Midya A.; Thomas D.G.; Malik S.; Pani A.K.
- Description
- Natural languages contain regular, context-free, and context-sensitive syntactic constructions, yet none of these classes of formal languages can be identified in the limit from positive examples. Mildly context-sensitive languages are capable to represent some context-sensitive constructions such as multiple agreement, crossed agreement, and duplication. These languages are important for natural language applications due to their expressiveness, and the fact that they are not fully context-sensitive. In this paper, we present a polynomial-time algorithm for inferring subclasses of internal contextual languages using positive examples only, namely strictly and k-uniform internal contextual languages with local maximum selectors which can contain mildly context-sensitive languages. 2017, Springer International Publishing AG.
- Source
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol-10580 LNCS, pp. 174-191.
- Date
- 2017-01-01
- Publisher
- Springer Verlag
- Subject
- Identification in the limit from positive data; Internal contextual grammar with local maximum selectors
- Coverage
- Midya A., Computer Science and Engineering, Icfai Tech School, Hyderabad, 501203, India; Thomas D.G., Department of Mathematics, Madras Christian College, Chennai, 600059, India; Malik S., Computer Science and Engineering, Alliance University, Bangalore, 562106, India; Pani A.K., Computer Science and Engineering, Faculty of Engineering, Christ University, Bangalore, 560074, India
- Rights
- Restricted Access
- Relation
- ISSN: 3029743; ISBN: 978-331967728-6
- Format
- Online
- Language
- English
- Type
- Conference paper
Collection
Citation
Midya A.; Thomas D.G.; Malik S.; Pani A.K., “Polynomial time learner for inferring subclasses of internal contextual grammars with local maximum selectors,” CHRIST (Deemed To Be University) Institutional Repository, accessed February 24, 2025, https://archives.christuniversity.in/items/show/20930.