Search

• < Previous
• 1
• Next >

---

Reachability Problem for Weak Multi-Pushdown Automata

Wojciech Czerwiński ; Piotr Hofman ; SŁawomir Lasota.

This paper is about reachability analysis in a restricted subclass of multi-pushdown automata. We assume that the control states of an automaton are partially ordered, and all transitions of an automaton go downwards with respect to the order. We prove decidability of the reachability problem, and&nbsp;[&hellip;]

---

Automata theory in nominal sets

Mikołaj Bojańczyk ; Bartek Klin ; Sławomir Lasota.

We study languages over infinite alphabets equipped with some structure that can be tested by recognizing automata. We develop a framework for studying such alphabets and the ensuing automata theory, where the key role is played by an automorphism group of the alphabet. In the process, we generalize&nbsp;[&hellip;]

---

Determinisability of register and timed automata

Lorenzo Clemente ; Sławomir Lasota ; Radosław Piórkowski.

The deterministic membership problem for timed automata asks whether the timed language given by a nondeterministic timed automaton can be recognised by a deterministic timed automaton. An analogous problem can be stated in the setting of register automata. We draw the complete&nbsp;[&hellip;]

---