Vol 19 no. 3


1. Inkdots as advice for finite automata

Küçük, Uğur ; Say, A. C. Cem ; Yakaryılmaz, Abuzer.
We examine inkdots placed on the input string as a way of providing advice to finite automata, and establish the relations between this model and the previously studied models of advised finite automata. The existence of an infinite hierarchy of classes of languages that can be recognized with the […]
Section: Automata, Logic and Semantics

2. Tight Euler tours in uniform hypergraphs - computational aspects

Lonc, Zbigniew ; Naroski, Paweł ; Rzążewski, Paweł.
By a tight tour in a $k$-uniform hypergraph $H$ we mean any sequence of its vertices $(w_0,w_1,\ldots,w_{s-1})$ such that for all $i=0,\ldots,s-1$ the set $e_i=\{w_i,w_{i+1}\ldots,w_{i+k-1}\}$ is an edge of $H$ (where operations on indices are computed modulo $s$) and the sets $e_i$ for […]
Section: Analysis of Algorithms

3. Stammering tableaux

Josuat-Vergès, Matthieu.
The PASEP (Partially Asymmetric Simple Exclusion Process) is a probabilistic model of moving particles, which is of great interest in combinatorics, since it appeared that its partition function counts some tableaux. These tableaux have several variants such as permutations tableaux, alternative […]
Section: Combinatorics

4. Post-surjectivity and balancedness of cellular automata over groups

Capobianco, Silvio ; Kari, Jarkko ; Taati, Siamak.
We discuss cellular automata over arbitrary finitely generated groups. We call a cellular automaton post-surjective if for any pair of asymptotic configurations, every pre-image of one is asymptotic to a pre-image of the other. The well known dual concept is pre-injectivity: a cellular automaton […]
Section: Automata, Logic and Semantics

5. Irreversible 2-conversion set in graphs of bounded degree

Kynčl, Jan ; Lidický, Bernard ; Vyskočil, Tomáš.
An irreversible $k$-threshold process (also a $k$-neighbor bootstrap percolation) is a dynamic process on a graph where vertices change color from white to black if they have at least $k$ black neighbors. An irreversible $k$-conversion set of a graph $G$ is a subset $S$ of vertices of $G$ such […]
Section: Graph Theory

6. Refined Enumeration of Corners in Tree-like Tableaux

Yan, Sherry H. F. ; Zhou, Robin D. P..
Tree-like tableaux are certain fillings of Ferrers diagrams originally introduced by Aval et al., which are in simple bijections with permutation tableaux coming from Postnikov's study of totally nonnegative Grassmanian and alternative tableaux introduced by Viennot. In this paper, we confirm […]
Section: Combinatorics

7. Tight upper bound on the maximum anti-forcing numbers of graphs

Shi, Lingjuan ; Zhang, Heping.
Let $G$ be a simple graph with a perfect matching. Deng and Zhang showed that the maximum anti-forcing number of $G$ is no more than the cyclomatic number. In this paper, we get a novel upper bound on the maximum anti-forcing number of $G$ and investigate the extremal graphs. If $G$ has a perfect […]
Section: Graph Theory

8. Binary Codes and Period-2 Orbits of Sequential Dynamical Systems

Defant, Colin.
Let $[K_n,f,\pi]$ be the (global) SDS map of a sequential dynamical system (SDS) defined over the complete graph $K_n$ using the update order $\pi\in S_n$ in which all vertex functions are equal to the same function $f\colon\mathbb F_2^n\to\mathbb F_2^n$. Let $\eta_n$ denote the maximum number of […]
Section: Combinatorics