5 citations · 15 across the 10 of their papers we have counts for
10 papers
A parallel parser for regular expressions
Angelo Borsotti, Luca Breveglieri, Stefano Crespi Reghizzi +1
Regular expression (RE) matching is a very common functionality that scans a text to find occurrences of patterns specified by an RE; it includes the simpler function of RE recogni…
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…
Higher-Order Operator Precedence Languages
Stefano Crespi Reghizzi, Matteo Pradella
Floyd's Operator Precedence (OP) languages are a deterministic context-free family having many desirable properties. They are locally and parallely parsable, and languages having a…
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…
Parsing methods streamlined
Luca Breveglieri, Stefano Crespi Reghizzi, Angelo Morzenti
This paper has the goals (1) of unifying top-down parsing with shift-reduce parsing to yield a single simple and consistent framework, and (2) of producing provably correct parsing…
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…
A unifying approach to picture grammars
Matteo Pradella, Alessandra Cherubini, Stefano Crespi Reghizzi
Several old and recent classes of picture grammars, that variously extend context-free string grammars in two dimensions, are based on rules that rewrite arrays of pixels. Such gra…
Algebraic properties of structured context-free languages: old approaches and novel developments
Stefano Crespi Reghizzi, Dino Mandrioli
The historical research line on the algebraic properties of structured CF languages initiated by McNaughton's Parenthesis Languages has recently attracted much renewed interest wit…