5 results
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
Piotr Hofman ; Slawomir Lasota ; Richard Mayr ; Patrick Totzke.
One-counter nets (OCN) are finite automata equipped with a counter that can store non-negative integer values, and that cannot be tested for zero. Equivalently, these are exactly 1-dimensional vector addition systems with states. We show that both strong and weak simulation preorder on OCN are […]
Published on March 14, 2016
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
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