BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Victor Poupet

Victor Poupet appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Formal Languages and Automata Theorynlin.CGDiscrete MathematicsComputational Complexity

Catalog footprint

What is connected

8works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

8 published item(s)

preprint2016arXiv

5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal

We study two-dimensional rotation-symmetric number-conserving cellular automata working on the von Neumann neighborhood (RNCA). It is known that such automata with 4 states or less are trivial, so we investigate the possible rules with 5 states. We give a full characterization of these automata and show that they cannot be strongly Turing universal. However, we give example of constructions that allow to embed some boolean circuit elements in a 5-states RNCA.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods

Linear acceleration theorems are known for most computational models. Although such results have been proved for two-dimensional cellular automata working on specific neighborhoods, no general construction was known. We present here a technique of linear acceleration for all two-dimensional languages recognized by cellular automata working on complete neighborhoods.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Comparing 1D and 2D Real Time on Cellular Automata

We study the influence of the dimension of cellular automata (CA) for real time language recognition of one-dimensional languages with parallel input. Specifically, we focus on the question of determining whether every language that can be recognized in real time on a 2-dimensional CA working on the Moore neighborhood can also be recognized in real time by a 1-dimensional CA working on the standard two-way neighborhood. We show that 2-dimensional CA in real time can perform a linear number of simulations of a 1-dimensional real time CA. If the two classes are equal then the number of simulated instances can be polynomial.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

L-Convex Polyominoes are Recognizable in Real Time by 2D Cellular Automata

A polyomino is said to be L-convex if any two of its cells are connected by a 4-connected inner path that changes direction at most once. The 2-dimensional language representing such polyominoes has been recently proved to be recognizable by tiling systems by S. Brocchi, A. Frosini, R. Pinzani and S. Rinaldi. In an attempt to compare recognition power of tiling systems and cellular automata, we have proved that this language can be recognized by 2-dimensional cellular automata working on the von Neumann neighborhood in real time. Although the construction uses a characterization of L-convex polyominoes that is similar to the one used for tiling systems, the real time constraint which has no equivalent in terms of tilings requires the use of techniques that are specific to cellular automata.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

$μ$-Limit Sets of Cellular Automata from a Computational Complexity Perspective

This paper concerns $μ$-limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial $μ$-random configuration. More precisely, we investigate the computational complexity of these sets and of related decision problems. Main results: first, $μ$-limit sets can have a $Σ\_3^0$-hard language, second, they can contain only $α$-complex configurations, third, any non-trivial property concerning them is at least $Π\_3^0$-hard. We prove complexity upper bounds, study restrictions of these questions to particular classes of CA, and different types of (non-)convergence of the measure of a word during the evolution.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings

In this paper we investigate certain properties of semi-totalistic cellular automata (CA) on the well known quasi-periodic kite and dart two dimensional tiling of the plane presented by Roger Penrose. We show that, despite the irregularity of the underlying grid, it is possible to devise a semi-totalistic CA capable of simulating any boolean circuit on this aperiodic tiling.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Directional Dynamics along Arbitrary Curves in Cellular Automata

This paper studies directional dynamics in cellular automata, a formalism previously introduced by the third author. The central idea is to study the dynamical behaviour of a cellular automaton through the conjoint action of its global rule (temporal action) and the shift map (spacial action): qualitative behaviours inherited from topological dynamics (equicontinuity, sensitivity, expansivity) are thus considered along arbitrary curves in space-time. The main contributions of the paper concern equicontinuous dynamics which can be connected to the notion of consequences of a word. We show that there is a cellular automaton with an equicontinuous dynamics along a parabola, but which is sensitive along any linear direction. We also show that real numbers that occur as the slope of a limit linear direction with equicontinuous dynamics in some cellular automaton are exactly the computably enumerable numbers.

0 citations0 reviewsNo code linkedOpen access