Star-height of Parikh images is bounded by 2 for one-register automata but the rational conjecture fails for multiple registers, showing Parikh's theorem does not hold over infinite alphabets.
On Context-Free Languages
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
fields
cs.FL 3verdicts
UNVERDICTED 3representative citing papers
Generalization of Z3-Noodler's stabilization method to transducers enables efficient solving of relational string constraints and outperforms prior solvers by solving more instances orders of magnitude faster.
Framework using abstract grammar transformations, theory-based algorithms, and graph-inspired canonization to detect and explain (in-)equivalence of context-free grammars, evaluated on educational datasets.
citing papers explorer
-
Star Complexity of Parikh Images of Languages over Infinite Alphabets
Star-height of Parikh images is bounded by 2 for one-register automata but the rational conjecture fails for multiple registers, showing Parikh's theorem does not hold over infinite alphabets.
-
String Solving with Stabilization and Transducers (Technical Report)
Generalization of Z3-Noodler's stabilization method to transducers enables efficient solving of relational string constraints and outperforms prior solvers by solving more instances orders of magnitude faster.
-
Detecting and Explaining (In-)equivalence of Context-Free Grammars
Framework using abstract grammar transformations, theory-based algorithms, and graph-inspired canonization to detect and explain (in-)equivalence of context-free grammars, evaluated on educational datasets.