10 citations · 44 across the 22 of their papers we have counts for
5 papers · 1 filter
Unambiguous Forest Factorization
Paul Gastin, Shankara Narayanan Krishna
In this paper, we look at an unambiguous version of Simon's forest factorization theorem, a very deep result which has wide connections in algebra, logic and automata. Given a morp…
Reachability in timed automata with diagonal constraints
Paul Gastin, Sayan Mukherjee, B Srivathsan
We consider the reachability problem for timed automata having diagonal constraints (like x - y < 5) as guards in transitions. The best algorithms for timed automata proceed by enu…
It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before"
Benedikt Bollig, Marie Fortin, Paul Gastin
Message sequence charts (MSCs) naturally arise as executions of communicating finite-state machines (CFMs), in which finite-state processes exchange messages through unbounded FIFO…
Regular Transducer Expressions for Regular Transformations
Vrunda Dave, Paul Gastin, Krishna Shankara Narayanan
Functional MSO transductions, deterministic two-way transducers, as well as streaming string transducers are all equivalent models for regular functions. In this paper, we show tha…
Gossiping in Message-Passing Systems
Benedikt Bollig, Marie Fortin, Paul Gastin
We study the gossip problem in a message-passing environment: When a process receives a message, it has to decide whether the sender has more recent information on other processes…