Dynamical aspects of -machines

DOI10.1016/J.DISC.2023.113486arXiv2210.06075MaRDI QIDQ6098077FDOQ6098077

Authors: Giulio Cerbai 

Publication date: 12 June 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

permutation patternsstack sorting\(\sigma\)-machine

Mathematics Subject Classification ID

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

Cites Work

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

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)