17 citations · 45 across the 18 of their papers we have counts for
11 papers · 1 filter
Learning Shuffle Ideals with Membership Queries and Contrastive Examples
S. Mahmoud Mousawi, Pierluigi San Pietro, Sandra Zilles
This paper studies learning of shuffle ideals with membership queries as well as with contrastive queries---a form of membership query that reveals not only whether a selected word…
Guillotine and Tiling Cofiniteness in Unary Picture Languages
Pierluigi San Pietro, Stefano Crespi Reghizzi, Antonio Restivo
Motivated by the study of closure operations on picture languages, we ask when a set of unary tiles can generate all sufficiently large pictures either via repeated horizontal and…
TARZAN: A Region-Based Library for Forward and Backward Reachability of Timed Automata (Extended Version)
Andrea Manini, Matteo Rossi, Pierluigi San Pietro
The zone abstraction, widely adopted for its notable practical efficiency, is the de facto standard in the verification of Timed Automata (TA). Nonetheless, region-based abstractio…
Random Testing of Model Checkers for Timed Automata with Automated Oracle Generation
Andrea Manini, Matteo Rossi, Pierluigi San Pietro
A key challenge in formal verification, particularly in Model Checking, is ensuring the correctness of the verification tools. Erroneous results on complex models can be difficult…
On Decidability Timed Automata with 2 Parametric Clocks
Marcello M. Bersani, Matteo Rossi, Pierluigi San Pietro
In this paper, we introduce a restriction of Timed Automata (TA), called non-resetting test Timed Automata (nrtTA). An nrtTA does not allow to test and reset the same clock on the…
Two-dimensional Dyck words
Stefano Crespi Reghizzi, Antonio Restivo, Pierluigi San Pietro
We propose different ways of lifting the notion of Dyck language from words to 2-dimensional (2D) pictures, by means of new definitions of increasing comprehensiveness. Two of the…
Reducing the local alphabet size in tiling systems by means of 2D comma-free codes
Stefano {Crespi Reghizzi}, Antonio Restivo, Pierluigi {San Pietro}
A recognizable picture language is defined as the projection of a local picture language defined by a set of two-by-two tiles, i.e. by a strictly-locally-testable (SLT) language of…
Deque languages, automata and planar graphs
Stefano Crespi Reghizzi, Pierluigi San Pietro
The memory of a deque (double ended queue) automaton is more general than a queue or two stacks; to avoid overgeneralization, we consider quasi-real-time operation. Normal forms of…
Non-erasing Chomsky-Sch{ü}tzenberger theorem with grammar-independent alphabet
Stefano Crespi Reghizzi, Pierluigi San Pietro
The famous theorem by Chomsky and Schützenberger (CST) says that every context-free language over an alphabet is representable as , where is a Dyck languag…
Commutative Languages and their Composition by Consensual Methods
Stefano Crespi Reghizzi, Pierluigi San Pietro
Commutative languages with the semilinear property (SLIP) can be naturally recognized by real-time NLOG-SPACE multi-counter machines. We show that unions and concatenations of such…
From Regular to Strictly Locally Testable Languages
Stefano Crespi Reghizzi, Pierluigi San Pietro
A classical result (often credited to Y. Medvedev) states that every language recognized by a finite automaton is the homomorphic image of a local language, over a much larger so-c…