BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Enrico Formenti

Enrico Formenti contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Formal Languages and Automata TheoryDiscrete Mathematicsnlin.CGData Structures and Algorithmsmath.ACmath.COmath.DS

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
9works
0followers
7topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2022arXiv

An Enumeration Algorithm for Binary Coprime Polynomials with Nonzero Constant Term

We address the enumeration of coprime polynomial pairs over $\F_2$ where both polynomials have a nonzero constant term, motivated by the construction of orthogonal Latin squares via cellular automata. To this end, we leverage on Benjamin and Bennett's bijection between coprime and non-coprime pairs, which is based on the sequences of quotients visited by dilcuE's algorithm (i.e. Euclid's algorithm ran backward). This allows us to break our analysis of the quotients in three parts, namely the enumeration and count of: (1) sequences of constant terms, (2) sequences of degrees, and (3) sequences of intermediate terms. For (1), we show that the sequences of constant terms form a regular language, and use classic results from algebraic language theory to count them. Concerning (2), we remark that the sequences of degrees correspond to compositions of natural numbers, which have a simple combinatorial description. Finally, we show that for (3) the intermediate terms can be freely chosen. Putting these three obeservations together, we devise a combinatorial algorithm to enumerate all such coprime pairs of a given degree, and present an alternative derivation of their counting formula.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Integrality of matrices, finiteness of matrix semigroups, and dynamics of linear and additive cellular automata

Let $\mathbb{K}$ be a finite commutative ring, and let $\mathbb{L}$ be a commutative $\mathbb{K}$-algebra. Let $A$ and $B$ be two $n \times n$-matrices over $\mathbb{L}$ that have the same characteristic polynomial. The main result of this paper states that the set $\left\{ A^0,A^1,A^2,\ldots\right\}$ is finite if and only if the set $\left\{ B^0,B^1,B^2,\ldots\right\}$ is finite. We apply this result to Cellular Automata (CA). Indeed, it gives a complete and easy-to-check characterization of sensitivity to initial conditions and equicontinuity for linear CA over the alphabet $\mathbb{K}^n$ for $\mathbb{K} = \mathbb{Z}/m\mathbb{Z}$ i.e., CA in which the local rule is defined by $n\times n$-matrices with elements in $\mathbb{Z}/m\mathbb{Z}$. To prove our main result, we derive an integrality criterion for matrices that is likely of independent interest. Namely, let $\mathbb{K}$ be any commutative ring (not necessarily finite), and let $\mathbb{L}$ be a commutative $\mathbb{K}$-algebra. Consider any $n \times n$-matrix $A$ over $\mathbb{L}$. Then, $A \in \mathbb{L}^{n \times n}$ is integral over $\mathbb{K}$ (that is, there exists a monic polynomial $f \in \mathbb{K}\left[t\right]$ satisfying $f\left(A\right) = 0$) if and only if all coefficients of the characteristic polynomial of $A$ are integral over $\mathbb{K}$. The proof of this fact relies on a strategic use of exterior powers (a trick pioneered by Gert Almkvist). Furthermore, we extend the decidability result concerning sensitivity and equicontinuity to the wider class of additive CA over a finite abelian group. For such CA, we also prove the decidability of injectivity, surjectivity, topological transitivity and all the properties (as, for instance, ergodicity) that are equivalent to the latter.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Non-maximal sensitivity to synchronism in periodic elementary cellular automata: exact asymptotic measures

In [11] and [13] the authors showed that elementary cellular automata rules 0, 3, 8, 12, 15, 28, 32, 34, 44, 51, 60, 128, 136, 140, 160, 162, 170, 200 and 204 (and their conjugation, reflection, reflected-conjugation) are not maximum sensitive to synchronism, i.e. they do not have a different dynamics for each (non-equivalent) block-sequential update schedule (defined as ordered partitions of cell positions). In this work we present exact measurements of the sensitivity to synchronism for these rules, as functions of the size. These exhibit a surprising variety of values and associated proof methods, such as the special pairs of rule 128, and the connection to the bissection of Lucas numbers of rule 8.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Complexity of the dynamics of reaction systems

Reaction systems are discrete dynamical systems inspired by bio-chemical processes, whose dynamical behaviour is expressed by set-theoretic operations on finite sets. Reaction systems thus provide a description of bio-chemical phenomena that complements the more traditional approaches, for instance those based on differential equations. A comprehensive list of decision problems about the dynamical behavior of reaction systems (such as cycles and fixed/periodic points, attractors, and reachability) is provided along with the corresponding computational complexity, which ranges from tractable problems to PSPACE-complete problems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Acceptance conditions for omega-languages and the Borel hierarchy

This paper investigates acceptance conditions for finite automata recognizing omega-regular languages. As a first result, we show that, under any acceptance condition that can be defined in the MSO logic, a finite automaton can recognize at most omega-regular languages. Starting from this, the paper aims at classifying acceptance conditions according to their expressive power and at finding the exact position of the classes of omega-languages they induced according to the Borel hierarchy. A new interesting acceptance condition is introduced and fully characterized. A step forward is also made in the understanding of the expressive power of (fin, =).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires

This volume contains the proceedings of the 18th International workshop AUTOMATA and the 3rd international symposium JAC. AUTOMATA workshop series aims at gathering researchers from all over the world working in fundamental aspects of cellular automata and related discrete complex systems. Topics cover (although they are not limited to): dynamics, topological, ergodic and algebraic aspects, algorithmic and complexity issues, emergent properties, formal language processing, symbolic dynamics, models of parallelism and distributed systems, phenomenological descriptions, scientific modeling and practical applications. JAC (Journées Automates Cellulaires) is a bi-annual symposium covering the same topics and was created to have a very high standard international conference in the domain. This one will be the third event of the series after Uzès (2008, France), Turku (2010, Finland).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Computational Aspects of Asynchronous CA

This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are "universal", i.e., allowing a (specific family of) ACA to simulate any TM on any input. We also consider the computational cost of such simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Non-uniform cellular automata and distributions of rules

In this paper we study $ν$-CA on one-dimensional lattice defined over a finite set of local rules. The main goal is to determine how the local rules can be mixed to ensure the produced $ν$-CA has some properties. In a first part, we give some background for the study of $ν$-CA. Then surjectivity and injectivity are studied using a variant of DeBruijn graphs. The next part is dedicated to the number-conserving property.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Non-Uniform Cellular Automata: classes, dynamics, and decidability

The dynamical behavior of non-uniform cellular automata is compared with the one of classical cellular automata. Several differences and similarities are pointed out by a series of examples. Decidability of basic properties like surjectivity and injectivity is also established. The final part studies a strong form of equicontinuity property specially suited for non-uniform cellular automata.

0 citations0 reviewsNo code linkedOpen access