A Bionic Natural Language Parser Equivalent to a Pushdown Automaton

• URL: http://arxiv.org/abs/2404.17343v1
• Date: Fri, 26 Apr 2024 11:50:15 GMT
• Title: A Bionic Natural Language Parser Equivalent to a Pushdown Automaton
• Authors: Zhenghao Wei, Kehua Lin, Jianlin Feng,
• Abstract summary: We propose a new bionic natural language (BNLP) based on Assembly Calculus (AC) In contrast to the original, the BNLP can fully handle all regular languages and Dyck languages. We formally prove that for any PDA, a Automaton corresponding to BNLP can always be formed.
• Score: 0.7783262415147654
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Assembly Calculus (AC), proposed by Papadimitriou et al., aims to reproduce advanced cognitive functions through simulating neural activities, with several applications based on AC having been developed, including a natural language parser proposed by Mitropolsky et al. However, this parser lacks the ability to handle Kleene closures, preventing it from parsing all regular languages and rendering it weaker than Finite Automata (FA). In this paper, we propose a new bionic natural language parser (BNLP) based on AC and integrates two new biologically rational structures, Recurrent Circuit and Stack Circuit which are inspired by RNN and short-term memory mechanism. In contrast to the original parser, the BNLP can fully handle all regular languages and Dyck languages. Therefore, leveraging the Chomsky-Sch \H{u}tzenberger theorem, the BNLP which can parse all Context-Free Languages can be constructed. We also formally prove that for any PDA, a Parser Automaton corresponding to BNLP can always be formed, ensuring that BNLP has a description ability equal to that of PDA and addressing the deficiencies of the original parser.

Related papers

• Compositional Program Generation for Few-Shot Systematic Generalization [59.57656559816271]
  This study on a neuro-symbolic architecture called the Compositional Program Generator (CPG) CPG has three key features: textitmodularity, textitcomposition, and textitabstraction, in the form of grammar rules. It perfect achieves generalization on both the SCAN and COGS benchmarks using just 14 examples for SCAN and 22 examples for COGS.
  arXiv  Detail & Related papers  (2023-09-28T14:33:20Z)
• A Biologically Plausible Parser [1.8563342761346613]
  We describe a of English effectuated by biologically plausible neurons and synapses. We demonstrate that this device is capable of correctly parsing reasonably nontrivial sentences.
  arXiv  Detail & Related papers  (2021-08-04T17:27:06Z)
• The Limitations of Limited Context for Constituency Parsing [27.271792317099045]
  Parsing-Reading-Predict architecture of (Shen et al., 2018a) was first to perform unsupervised syntactic parsing. What kind of syntactic structure can current neural approaches to syntax represent? We ground this question in the sandbox of probabilistic-free-grammars (PCFGs) We identify a key aspect of the representational power of these approaches: the amount and directionality of context that the predictor has access to.
  arXiv  Detail & Related papers  (2021-06-03T03:58:35Z)
• Dependency Parsing with Bottom-up Hierarchical Pointer Networks [0.7412445894287709]
  Left-to-right and top-down transition-based algorithms are among the most accurate approaches for performing dependency parsing. We propose two novel transition-based alternatives: an approach that parses a sentence in right-to-left order and a variant that does it from the outside in. We empirically test the proposed neural architecture with the different algorithms on a wide variety of languages, outperforming the original approach in practically all of them.
  arXiv  Detail & Related papers  (2021-05-20T09:10:42Z)
• Zero-Shot Cross-lingual Semantic Parsing [56.95036511882921]
  We study cross-lingual semantic parsing as a zero-shot problem without parallel data for 7 test languages. We propose a multi-task encoder-decoder model to transfer parsing knowledge to additional languages using only English-Logical form paired data. Our system frames zero-shot parsing as a latent-space alignment problem and finds that pre-trained models can be improved to generate logical forms with minimal cross-lingual transfer penalty.
  arXiv  Detail & Related papers  (2021-04-15T16:08:43Z)
• Revisiting Language Encoding in Learning Multilingual Representations [70.01772581545103]
  We propose a new approach called Cross-lingual Language Projection (XLP) to replace language embedding. XLP projects the word embeddings into language-specific semantic space, and then the projected embeddings will be fed into the Transformer model. Experiments show that XLP can freely and significantly boost the model performance on extensive multilingual benchmark datasets.
  arXiv  Detail & Related papers  (2021-02-16T18:47:10Z)
• Strongly Incremental Constituency Parsing with Graph Neural Networks [70.16880251349093]
  Parsing sentences into syntax trees can benefit downstream applications in NLP. Transition-baseds build trees by executing actions in a state transition system. Existing transition-baseds are predominantly based on the shift-reduce transition system.
  arXiv  Detail & Related papers  (2020-10-27T19:19:38Z)
• SKATE: A Natural Language Interface for Encoding Structured Knowledge [3.7296147370114183]
  In Natural Language (NL) applications, there is often a mismatch between what the NL interface is capable of interpreting and what a lay user knows how to express. This work describes a novel natural language interface that reduces this mismatch by refining natural language input through successive, automatically generated semi-structured templates.
  arXiv  Detail & Related papers  (2020-10-20T20:13:09Z)
• RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
  We show that RNNs can efficiently generate bounded hierarchical languages that reflect the scaffolding of natural language syntax. We introduce Dyck-($k$,$m$), the language of well-nested brackets (of $k$ types) and $m$-bounded nesting depth. We prove that an RNN with $O(m log k)$ hidden units suffices, an exponential reduction in memory, by an explicit construction.
  arXiv  Detail & Related papers  (2020-10-15T04:42:29Z)
• Phonological Features for 0-shot Multilingual Speech Synthesis [50.591267188664666]
  We show that code-switching is possible for languages unseen during training, even within monolingual models. We generate intelligible, code-switched speech in a new language at test time, including the approximation of sounds never seen in training.
  arXiv  Detail & Related papers  (2020-08-06T18:25:18Z)
• On the Linguistic Capacity of Real-Time Counter Automata [1.8072051868187933]
  We study the abilities of real-time counter machines as formal grammars. We show that counter languages are closed under complement, union, intersection, and many other common set operations. This work makes general contributions to the theory of formal languages that are of potential interest for understanding recurrent neural networks.
  arXiv  Detail & Related papers  (2020-04-15T03:37:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.