| 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. |
Similar Papers
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. |
Strong Equivalence of TAG and CCG (2021.tacl-1)
Copied to clipboard
| Challenge: | Tree-adjoining grammar and combinatory categorial grammar have the same expressive power on trees. |
| Approach: | Tree-adjoining grammar (TAG) and combinatory categorial grammar (CCG) are well-established grammars with the same expressive power on strings. |
| Outcome: | The proposed grammars have the same expressive power on trees as classical grammars and can express a limited amount of cross-serial dependencies and have the constant growth property. |
GRAMMAR-LLM: Grammar-Constrained Natural Language Generation (2025.findings-acl)
Copied to clipboard
| Challenge: | Existing approaches to fine-tuning and prompting are insufficient to ensure compliance with predefined taxonomies, syntactic structures, or domain-specific rules. |
| Approach: | They propose a framework that integrates formal grammatical constraints into the decoding process to enforce syntactic correctness in linear time while maintaining expressiveness in grammar rule definition. |
| Outcome: | The proposed framework enforces syntactic correctness in linear time while maintaining expressiveness in grammar rule definition. |
On Efficiently Representing Regular Languages as RNNs (2024.findings-acl)
Copied to clipboard
| Challenge: | Recent work by Hewitt et al. (2020) provides an interpretation of the empirical success of recurrent neural networks (RNNs) as language models (LMs). |
| Approach: | They generalize their construction and show that RNNs can efficiently represent a larger class of LMs than previously claimed. |
| Outcome: | The results suggest that RNNs can represent a larger class of LMs than previously claimed . |
Targeted Syntactic Evaluation on the Chomsky Hierarchy (2024.lrec-main)
Copied to clipboard
| Challenge: | a novel evaluation paradigm for targeted syntactic evaluations is proposed . we create formal languages that abstract four syntaktic phenomena in natural languages . |
| Approach: | They propose a new evaluation paradigm for Targeted Syntactic Evaluations . they create formal languages that abstract syntactical phenomena in natural languages . |
| Outcome: | The proposed evaluation paradigm evaluates language models on language modeling tasks . it shows that they can capture the structural patterns of the (Adj)n NP type formal language . |
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. |
Prefix Lexicalization of Synchronous CFGs using Synchronous TAG (P18-1)
Copied to clipboard
| Challenge: | epsilon-free, chain-free synchronous context-free grammars can be converted into weakly equivalent synchronous tree-adjoining grammars (STAGs) this transformation doubles the grammar’s rank and cubes its size, but in practice the size increase is only quadratic. |
| Approach: | They extend Greibach normal form from CFGs to SCFGs and prove new formal properties about SCFG, a formalism with many applications in natural language processing. |
| Outcome: | The proposed grammars achieve asymptotic and empirical speed improvements on a machine translation task. |
On the Intersection of Context-Free and Regular Languages (2023.eacl-main)
Copied to clipboard
| Challenge: | We generalize the Bar-Hillel intersection construction so that the given WFSA may contain -arcs. |
| Approach: | They propose a construction that generalizes the Bar- Hillel in the case the desired automaton has -arcs and generalize the weighted extension so that the given WFSA may contain arcs. |
| Outcome: | The proposed construction can encode the structure of both the input automaton and grammar while retaining the asymptotic size of the original construction. |
Do LLMs Adhere to Label Definitions? Examining Their Receptivity to External Label Definitions (2025.emnlp-main)
Copied to clipboard
Seyedali Mohammadi, Bhaskara Hanuma Vedula, Hemank Lamba, Edward Raff, Ponnurangam Kumaraguru, Francis Ferraro, Manas Gaur
| Challenge: | Exact label definitions are considered as clues to disambiguate unclear labels, helping models perform their tasks more effectively. |
| Approach: | They conducted controlled experiments on multiple explanation benchmark datasets and label definition conditions using expert-curated, LLM-generated, perturbed, and swapped definitions. |
| Outcome: | The results suggest that models often default to internal representations, particularly in general tasks, while domain-specific tasks benefit more from explicit definitions. |
Reasoning Up the Instruction Ladder for Controllable Language Models (2026.findings-acl)
Copied to clipboard
| Challenge: | Current models struggle to balance competing directives, causing conflicting instructions. |
| Approach: | They propose to reframe instruction hierarchy resolution as a reasoning task . they use a training dataset to enable this capability by transferring general reasoning capabilities to instruction prioritization . |
| Outcome: | The proposed method improves on safety-critical scenarios beyond the training distribution and jailbreaks. |