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.
LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 4roles
background 1polarities
background 1representative citing papers
Symmetric MOD_m circuits require subexponential size to compute n-ary AND, with the bound matched by known depth-2 constructions.
Preservation theorems hold for all lattice semirings but fail for tropical, Viterbi, Łukasiewicz, and natural semirings, while existential preservation holds on finite interpretations for lattices unlike the Boolean case.
Develops an affine calculus and higher-order quantitative logic with novel guarded recursion and induction principles over probability measures and naturals, illustrated on Markov processes and learning algorithms.
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.
-
Optimal Lower Bounds for Symmetric Modular Circuits
Symmetric MOD_m circuits require subexponential size to compute n-ary AND, with the bound matched by known depth-2 constructions.
-
Preservation Theorems in Semiring Semantics
Preservation theorems hold for all lattice semirings but fail for tropical, Viterbi, Łukasiewicz, and natural semirings, while existential preservation holds on finite interpretations for lattices unlike the Boolean case.
-
Induction and Recursion Principles in a Higher-Order Quantitative Logic for Probability
Develops an affine calculus and higher-order quantitative logic with novel guarded recursion and induction principles over probability measures and naturals, illustrated on Markov processes and learning algorithms.