@article{10.1145_3776686,
    author = {Nikhil Pimpalkhare and Zachary Kincaid and Thomas Reps},
    doi = {https://dx.doi.org/10.1145/3776686},
    title = {{Context-Free-Language Reachability for Almost-Commuting Transition Systems}},
    year = {2026},
    issue_date = {January 2026},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    volume = {10},
    number = {POPL},
    url = {https://doi.org/10.1145/3776686},
    abstract = {We extend the scope of context-free-language (CFL) reachability to a new class of infinite-state systems. Parikh’s Theorem is a useful tool for solving CFL-reachability problems for transition systems that consist of commuting transition relations. It implies that the image of a context-free language under a homomorphism into a commutative monoid is semi-linear, and that there is a linear-time algorithm for constructing a Presburger arithmetic formula that represents it. However, for many transition systems of interest, transitions do not commute. In this paper, we introduce almost-commuting transition systems, which pair finite-state control with commutative components, but which are in general not commutative. We extend Parikh’s theorem to show that the image of a context-free language under a homomorphism into an almost-commuting monoid is semi-linear and that there is a polynomial-time algorithm for constructing a Presburger arithmetic formula that represents it. This result yields a general framework for solving CFL-reachability problems over almost-commuting transition systems. We describe several examples of systems within this class. Finally, we examine closure properties of almost-commuting monoids that can be used to modularly compose almost-commuting transition systems while remaining in the class.},
    journal = {Proc. ACM Program. Lang.},
    month = {jan},
    articleno = {44},
    numpages = {26},
    date-added = {2026-1-9 10:37:19 +0100},
    date-modified = {2026-1-9 10:2:8 +0100},
    nextcloud = {https://yossarian.ddns.net:4843/nextcloud/index.php/apps/files/files?dir=/Library/bibliographer/./library/entries/10.1145_3776686/}
}

@article{10.1145_3776686, author = {Nikhil Pimpalkhare and Zachary Kincaid and Thomas Reps}, doi = {https://dx.doi.org/10.1145/3776686}, title = {{Context-Free-Language Reachability for Almost-Commuting Transition Systems}}, year = {2026}, issue_date = {January 2026}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, volume = {10}, number = {POPL}, url = {https://doi.org/10.1145/3776686}, abstract = {We extend the scope of context-free-language (CFL) reachability to a new class of infinite-state systems. Parikh’s Theorem is a useful tool for solving CFL-reachability problems for transition systems that consist of commuting transition relations. It implies that the image of a context-free language under a homomorphism into a commutative monoid is semi-linear, and that there is a linear-time algorithm for constructing a Presburger arithmetic formula that represents it. However, for many transition systems of interest, transitions do not commute. In this paper, we introduce almost-commuting transition systems, which pair finite-state control with commutative components, but which are in general not commutative. We extend Parikh’s theorem to show that the image of a context-free language under a homomorphism into an almost-commuting monoid is semi-linear and that there is a polynomial-time algorithm for constructing a Presburger arithmetic formula that represents it. This result yields a general framework for solving CFL-reachability problems over almost-commuting transition systems. We describe several examples of systems within this class. Finally, we examine closure properties of almost-commuting monoids that can be used to modularly compose almost-commuting transition systems while remaining in the class.}, journal = {Proc. ACM Program. Lang.}, month = {jan}, articleno = {44}, numpages = {26}, date-added = {2026-1-9 10:37:19 +0100}, date-modified = {2026-1-9 10:2:8 +0100}, nextcloud = {https://yossarian.ddns.net:4843/nextcloud/index.php/apps/files/files?dir=/Library/bibliographer/./library/entries/10.1145_3776686/} }