Dynamical aspects of -machines

DOI10.1016/J.DISC.2023.113486MaRDI QIDQ6098077zbMATH OpenFDO

Authors Giulio Cerbai

Publication date 12 June 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.06075

zbMATH Keywords

permutation patternsstack sorting\(\sigma\)-machine

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Theory of data (68Pxx)

Abstract: The $sigma$-machine was recently introduced by Cerbai, Claesson and Ferrari as a tool to gain a better insight on the problem of sorting permutations with two stacks in series. It consists of two consecutive stacks, which are restricted in the sense that their content must at all times avoid a certain pattern: a given $sigma$, in the first stack, and $21$, in the second. Here we prove that in most cases sortable permutations avoid a bivincular pattern $xi$. We provide a geometric decomposition of $xi$-avoiding permutations and use it to count them directly. Then we characterize the permutations with the property that the output of the $sigma$-avoiding stack does not contain $sigma$, which we call effective. For $sigma=123$, we obtain an alternative method to enumerate sortable permutations. Finally, we classify $sigma$-machines and determine the most challenging to be studied.

Recommendations

• On topological dynamics of Turing machines
• Dynamical systems and \(\sigma\)-symmetries
• Dynamical properties of hybrid automata
• Symbolic dynamics and finite automata
• scientific article; zbMATH DE number 919601
• Computability in Symbolic Dynamics
• Computable symbolic dynamics
• scientific article; zbMATH DE number 3609135
• On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts
• scientific article; zbMATH DE number 4074498

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• (2+2)-free posets, ascent sequences and pattern avoiding permutations
• 2-stack sorting is polynomial
• A survey of stack-sorting disciplines
• Catalan and Schröder permutations sortable by two restricted stacks
• Catalan intervals and uniquely sorted permutations
• Descents in \(t\)-sorted permutations
• Pattern avoidance in ascent sequences
• Restricted stacks as functions
• Sorted and/or sortable permutations
• Sorting Cayley permutations with pattern-avoiding machines
• Sorting twice through a stack
• Sorting with pattern-avoiding stacks: the 132-machine
• Stack sorting with increasing and decreasing stacks
• Stack sorting with restricted stacks
• Stack-sorting with consecutive-pattern-avoiding stacks
• Stack-sorting, set partitions, and Lassalle's sequence
• Transport of patterns by Burge transpose
• Two stacks in series: a decreasing stack followed by an increasing stack

This page was built for publication: Dynamical aspects of \(\sigma\)-machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098077)