Arrow Research search

Author name cluster

Lorenzo Clemente

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers
2 author rows

Possible papers

8

Highlights Conference 2024 Conference Abstract

Zeroness of weighted basic parallel processes

  • Lorenzo Clemente

[see the attached PDF for the same abstract + references] We study weighted basic parallel processes (WBPP), a nonlinear recursive generalisation of Schutzenberger's weighted finite automata inspired from process algebra and Petri net theory. Formally, they can be defined as communication free Petri nets, which means that each transition can remove a token from exactly one place; tokens can be added without restrictions. Each transition is labelled with a weight from a field, say the rationals $\mathbb Q$. The weight of a run is the product of the weights of the transitions occurring in the run; the weight of an input word is the sum of the weights of the runs accepting the word. (Alternatively, a WBPP can be seen as a weighted context-free grammar where the nonterminal symbols commute with each other.) Like BPP recognise languages $\subseteq \Sigma^ $, WBPP recognise series $\Sigma^ \to \mathbb Q$. The WBPP-recognisable series form an interesting class of series generalising the rational series (those recognised by weighted finite automata). For example, 1) they are effectively closed under many operations such as scalar product, sum, shuffle, shuffle-inverse, and derivation; 2) a version of the implicit functions theorem applies to them, which provides a very general way to construct WBPP series from previous ones; 3) the commutative subclass of WBPP series (i. e. , those for which the output weight does not depend on the order of the input symbols) corresponds to multivariate constructible differentially finite power series, introduced by Bergeron, Reutenauer, and Sattler in the context of combinatorial enumeration. Our main result is an algorithm of 2EXPSPACE complexity for the WBPP equivalence problem. While (unweighted) BPP language equivalence is undecidable, we can use this algorithm decide multiplicity equivalence of BPP and language equivalence of unambiguous BPP, with the same complexity. Decidability of the latter problems was not known before. The corresponding problems for weighted context-free grammars are open since a long time. The complexity analysis of the equivalence algorithm is based on effective bounds from algebraic geometry. More precisely, we study the length of chains of polynomial ideals constructed by repeated application of finitely many, not necessarily commuting derivations of a multivariate polynomial ring. This is obtained by generalising a result of Novikov and Yakovenko in the case of a single derivation. The fact that we obtain an elementary bound is noteworthy, since generic bounds on ideal chains are only non-primitive recursive in general.

Details

Highlights Conference 2023 Conference Abstract

Complexity of deciding equality of power series from combinatorial enumeration

  • Lorenzo Clemente

A power series is constructible differentially finite (CDF) if it satisfies a system of polynomial differential equations [Bergeron & Reutenauer 1990, Bergeron & Sattler 1995]. CDF series generalise algebraic power se- ries and find a natural application as exponential generating functions in combinatorial enumeration (e. g. , combinatorial species by Andre Joyal). For instance, the exponential generating functions of Bell numbers B(n), of rooted Cayley trees (sequence nn−1), of series-parallel graphs, and of languages of unordered trees defined by Parikh tree automata are CDF. Bergeron & Reutenauer observed that the equality problem for univari- ate CDF series is decidable, without providing a complexity bound. We show that zeroness of univariate CDF series can be solved in elementary (2-EXPTIME) complexity. The proof relies on a technical lemma from [Novikov & Yakovenko 1999] showing that chains of polynomial ideals generated by iterated Lie derivatives have at most doubly exponential length. We then extend this result in two directions. First, we show that the 2-EXPTIME complexity is retained for multivariate CDF. Second, we show that the problem is in PTIME for CDF satisfying a system of linear differential equations with constant coefficients. Along the way, we show that multivariate CDF is a very robust class with many pleasant closure properties. Contributed talk given by Lorenzo Clemente

Details

Highlights Conference 2018 Conference Abstract

Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms

  • Lorenzo Clemente

ABSTRACT. We study an expressive model of timed pushdown automata extended with modular and fractional clock constraints. We show that the binary reachability relation is effectively expressible in hybrid linear arithmetic with a rational and an integer sort. This subsumes analogous expressibility results previously known for finite and pushdown timed automata with untimed stack. As key technical tools, we use quantifier elimination for a fragment of hybrid linear arithmetic and for cyclic order atoms, and a reduction to register pushdown automata over cyclic order atoms. This is joint work with S. Lasota.

Details

Highlights Conference 2015 Conference Abstract

Reachability analysis of first-order definable pushdown systems

  • Lorenzo Clemente

We study pushdown systems where control states, stack alphabet, and transition relation, instead of being finite, are first-order definable in a fixed countably-infinite structure. We show that the reachability analysis can be addressed with the well-known saturation technique for the wide class of oligomorphic structures. Moreover, for the more restrictive homogeneous structures, we are able to give concrete complexity upper bounds. We show ample applicability of our technique by presenting several concrete examples of homogeneous structures, subsuming, with optimal complexity, known results from the literature. We show that infinitely many such examples of homogeneous structures can be obtained with the classical wreath product construction. This is joint work with Sławomir Lasota, from the University of Warsaw.

Details

CSL Conference 2015 Conference Paper

Reachability Analysis of First-order Definable Pushdown Systems

  • Lorenzo Clemente
  • Slawomir Lasota 0001

We study pushdown systems where control states, stack alphabet, and transition relation, instead of being finite, are first-order definable in a fixed countably-infinite structure. We show that the reachability analysis can be addressed with the well-known saturation technique for the wide class of oligomorphic structures. Moreover, for the more restrictive homogeneous structures, we are able to give concrete complexity upper bounds. We show ample applicability of our technique by presenting several concrete examples of homogeneous structures, subsuming, with optimal complexity, known results from the literature. We show that infinitely many such examples of homogeneous structures can be obtained with the classical wreath product construction.

Details