Papers by Alexandra Butoi
Convergence and Diversity in the Control Hierarchy (2023.acl-long)
Copied to clipboard
| Challenge: | Weir has defined a hierarchy of language classes whose second member (L2) is generated by tree-adjoining grammars (TAG), linear indexed grammars, combinatory categorial grammars and head grammars. |
| Approach: | They propose to extend Weir's mechanism of control to give a definition of controllable pushdown automata (PDAs) they propose to use a stricter notion of equivalence to allow for finer-grained comparisons than weak equvalence. |
| Outcome: | The proposed language classes are d-weakly equivalent to Weir's original two-level grammar, but not d strongly equivalent. |
Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages (2023.emnlp-main)
Copied to clipboard
| Challenge: | a class of tree-adjoining languages can be characterized by various two-level formalisms controlled by semiring-weighted CFGs and PDAs. |
| Approach: | They propose semiring-weighted versions of controllable CFGs and PDAs . they also introduce a WPDA normal form that is analogous to Chomsky's normal form for CFG . |
| Outcome: | The proposed algorithms are more time-efficient than the previous ones for LIG, PAA, and EPDA. |
Computational Expressivity of Neural Language Models (2024.acl-tutorials)
Copied to clipboard
| Challenge: | Language models (LMs) are at the forefront of NLP research due to their versatility across diverse tasks. |
| Approach: | This tutorial will provide a framework for formal analysis of modern language models using tools from formal language theory. |
| Outcome: | This tutorial will provide a framework for formal analysis of modern language models using tools from formal language theory (FLT). |
On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning (2024.acl-long)
Copied to clipboard
| Challenge: | Existing theoretical treatments have shed light on some aspects of CoT, but we are still far from a concrete understanding of the concept. |
| Approach: | They propose to formalize CoT reasoning in a probabilistic setting to bridge this gap . they show that LMs can represent the same family of distributions over strings as probabilistic Turing machines. |
| Outcome: | The proposed model can represent the same family of distributions over strings as Turing machines. |
Algorithms for Weighted Pushdown Automata (2022.emnlp-main)
Copied to clipboard
| Challenge: | Existing dynamic programming algorithms for PDAs often resort to a PDA-to-CFG conversion. |
| Approach: | They propose to use a pushdown automaton to reduce the space requirements by a factor of |Gamma| or the runtime by reducing the number of states. |
| Outcome: | The proposed algorithms reduce the space requirements by a factor of |Gamma| or reduce the runtime by fewer states. |