5 results
Wojciech Czerwiński ; Sławomir Lasota.
The regular separability problem asks, for two given languages, if there exists a regular language including one of them but disjoint from the other. Our main result is decidability, and PSpace-completeness, of the regular separability problem for languages of one counter automata without zero tests […]
Published on June 11, 2019
Mikołaj Bojańczyk ; Sławomir Lasota.
We define a new kind of automata recognizing properties of data words or data trees and prove that the automata capture all queries definable in Regular XPath. We show that the automata-theoretic approach may be applied to answer decidability and expressibility questions for XPath.
Published on February 16, 2012
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 […]
Published on August 15, 2014
Khadijeh Keshvardoost ; Bartek Klin ; Sławomir Lasota ; Joanna Ochremiak ; Szymon Toruńczyk.
We investigate the isomorphism problem in the setting of definable sets (equivalent to sets with atoms): given two definable relational structures, are they related by a definable isomorphism? Under mild assumptions on the underlying structure of atoms, we prove decidability of the problem. The core […]
Published on December 11, 2019
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 […]
Published on May 10, 2022