More Like this

1. Temporal Reasoning with Kinodynamic Networks

   Zhang, Han; Tiruviluamala, Neelesh; Koenig, Sven; Kumar, T. K. (January 2021, International Conference on Automated Planning and Scheduling)

   null (Ed.)

   Temporal reasoning is central to Artificial Intelligence (AI) and many of its applications. However, the existing algorithmic frameworks for temporal reasoning are not expressive enough to be applicable to robots with complex kinodynamic constraints typically described using differential equations. For example, while minimum and maximum velocity constraints can be encoded in Simple Temporal Networks (STNs), higher-order kinodynamic constraints cannot be represented in existing frameworks. In this paper, we present a novel framework for temporal reasoning called Kinodynamic Networks (KDNs). KDNs combine elements of existing temporal reasoning frameworks with the idea of Bernstein polynomials. The velocity profiles of robots are represented using Bernstein polynomials; and dynamic constraints on these velocity profiles can be converted to linear constraints on the to-be-determined coefficients of their Bernstein polynomials. We study KDNs for their attractive theoretical properties and apply them to the Multi-Agent Path Finding (MAPF) problem with higher-order kinodynamic constraints. We show that our approach is not only scalable but also yields smooth velocity profiles for all robots that can be executed by their controllers. 

   more » « less
2. Automata for subregular syntax: Syntax with strings attached

   https://doi.org/10.7275/scil.3184  

   Graf, Thomas; Hanson, Kenneth (January 2025, Proceedings of the Society for Computation in Linguistics)

   Building on recent work in subregular syntax, we argue that syntactic constraints are best understood as operating not over trees, but rather strings that track structural relations such as dominance and c-command. Even constraints that seem intrinsically tied to trees (e.g. constraints on tree tiers) can be reduced to such strings. We define serial constraints as an abstraction that decomposes string constraints into a context function (which associates nodes with strings) and a requirement function (which enforces constraints on these strings). We provide a general procedure for implementing serial constraints as deterministic tree automata. The construction reveals that the many types of constraints found in subregular syntax are variants of the same computational template. Our findings open up a string-based perspective on syntactic constraints and provide a new, very general approach to the automata-theoretic study of subregular complexity. 

   more » « less
3. SoK: A Literature and Engineering Review of Regular Expression Denial of Service (ReDoS)

   Bhuiyan, Masudul; Cakar, Berk; Burmans, Ethan H; Davis, James C; Staicu, Cristian-Alexandru (August 2025, The 20th ACM ASIA Conference on Computer and Communications Security (ACM ASIACCS 2025))

   Regular Expression Denial of Service (ReDoS) is a vulnerability class that has become prominent in recent years. Attackers can weaponize such weaknesses as part of asymmetric cyberattacks that exploit the slow worst-case matching time of regular expres- sion (regex) engines. In the past, problematic regular expressions have led to outages at Cloudflare and Stack Overflow, showing the severity of the problem. While ReDoS has drawn significant research attention, there has been no systematization of knowledge to delineate the state of the art and identify opportunities for fur- ther research. In this paper, we describe the existing knowledge on ReDoS. We first provide a systematic literature review, discussing approaches for detecting, preventing, and mitigating ReDoS vul- nerabilities. Then, our engineering review surveys the latest regex engines to examine whether and how ReDoS defenses have been re- alized. Combining our findings, we observe that (1) in the literature, almost no studies evaluate whether and how ReDoS vulnerabilities can be weaponized against real systems, making it difficult to assess their real-world impact; and (2) from an engineering view, many mainstream regex engines now have ReDoS defenses, rendering many threat models obsolete. We conclude with an extensive dis- cussion, highlighting avenues for future work. The open challenges in ReDoS research are to evaluate emerging defenses and support engineers in migrating to defended engines. We also highlight the parallel between performance bugs and asymmetric DoS, and we argue that future work should capitalize more on this similarity and adopt a more systematic view on ReDoS-like vulnerabilities. 

   more » « less
4. Sequential language-based decisions

   A. Bjorndahl; J. Y. Halpern (June 2023, Proceedings of Nineteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK))

   In earlier work, we introduced the framework of language-based decisions, the core idea of which was to modify Savage's classical decision-theoretic framework by taking actions to be descriptions in some language, rather than functions from states to outcomes, as they are defined classically. Actions had the form ``if psi then do phi''', where psi and phi$ were formulas in some underlying language, specifying what effects would be brought about under what circumstances. The earlier work allowed only one-step actions. But, in practice, plans are typically composed of a sequence of steps. Here, we extend the earlier framework to \emph{sequential} actions, making it much more broadly applicable. Our technical contribution is a representation theorem in the classical spirit: agents whose preferences over actions satisfy certain constraints can be modeled as if they are expected utility maximizers. As in the earlier work, due to the language-based specification of the actions, the representation theorem requires a construction not only of the probability and utility functions representing the agent's beliefs and preferences, but also the state and outcomes spaces over which these are defined, as well as a ``selection function'' which intuitively captures how agents disambiguate coarse descriptions. The (unbounded) depth of action sequencing adds substantial interest (and complexity!) to the proof. 

   more » « less
5. Collapse of complexity of brain and body activity due to excessive inhibition and MeCP2 disruption

   https://doi.org/10.1073/pnas.2106378118  

   Li, Jingwen; Kells, Patrick A.; Osgood, Ayla C.; Gautam, Shree Hari; Shew, Woodrow L. (October 2021, Proceedings of the National Academy of Sciences)

   null (Ed.)

   Complex body movements require complex dynamics and coordination among neurons in motor cortex. Conversely, a long-standing theoretical notion supposes that if many neurons in motor cortex become excessively synchronized, they may lack the necessary complexity for healthy motor coding. However, direct experimental support for this idea is rare and underlying mechanisms are unclear. Here we recorded three-dimensional body movements and spiking activity of many single neurons in motor cortex of rats with enhanced synaptic inhibition and a transgenic rat model of Rett syndrome (RTT). For both cases, we found a collapse of complexity in the motor system. Reduced complexity was apparent in lower-dimensional, stereotyped brain–body interactions, neural synchrony, and simpler behavior. Our results demonstrate how imbalanced inhibition can cause excessive synchrony among movement-related neurons and, consequently, a stereotyped motor code. Excessive inhibition and synchrony may underlie abnormal motor function in RTT. 

   more » « less