Search

• < Previous
• 1
• Next >

---

Minimisation of Multiplicity Tree Automata

Stefan Kiefer ; Ines Marusic ; James Worrell.

We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polynomial time assuming unit-cost arithmetic. We also show that a polynomial bound in the standard Turing model would require&nbsp;[&hellip;]

---

On the Expressiveness and Monitoring of Metric Temporal Logic

Hsi-Ming Ho ; Joël Ouaknine ; James Worrell.

It is known that Metric Temporal Logic (MTL) is strictly less expressive than the Monadic First-Order Logic of Order and Metric (FO[<, +1]) when interpreted over timed words; this remains true even when the time domain is bounded a priori. In this work, we present an extension of MTL with the same&nbsp;[&hellip;]

---

On the decidability and complexity of Metric Temporal Logic over finite words

Joel Ouaknine ; James Worrell.

Metric Temporal Logic (MTL) is a prominent specification formalism for real-time systems. In this paper, we show that the satisfiability problem for MTL over finite timed words is decidable, with non-primitive recursive complexity. We also consider the model-checking problem for MTL: whether all&nbsp;[&hellip;]

---