28 citations · 75 across the 20 of their papers we have counts for
6 papers · 1 filter
Reachability relations of timed pushdown automata
Lorenzo Clemente, Sławomir Lasota
Timed pushdown automata (TPDA) are an expressive formalism combining recursion with a rich logic of timing constraints. We prove that reachability relations of TPDA are expressible…
On the Complexity of the Universality and Inclusion Problems for Unambiguous Context-Free Grammars
Lorenzo Clemente
We study the computational complexity of universality and inclusion problems for unambiguous finite automata and context-free grammars. We observe that several such problems can be…
Determinisability of one-clock timed automata
Lorenzo Clemente, Sławomir Lasota, Radosław Piórkowski
The deterministic membership problem for timed automata asks whether the timed language recognised by a nondeterministic timed automaton can be recognised by a deterministic timed…
On the complexity of the universality and inclusion problems for unambiguous context-free grammars (technical report)
Lorenzo Clemente
We study the computational complexity of universality and inclusion problems for unambiguous finite automata and context-free grammars. We observe that several such problems can be…
Timed games and deterministic separability
Lorenzo Clemente, Sławomir Lasota, Radosław Piórkowski
We study a generalisation of Büchi-Landweber games to the timed setting. The winning condition is specified by a non-deterministic timed automaton with epsilon transitions and only…
Cost Automata, Safe Schemes, and Downward Closures
David Barozzini, Lorenzo Clemente, Thomas Colcombet +1
In this work we prove decidability of the model-checking problem for safe recursion schemes against properties defined by alternating B-automata. We then exploit this result to sho…