Combinatorial problems of commutation and rearrangements
From MaRDI portal
Publication:2536784
DOI10.1007/BFb0079468zbMath0186.30101MaRDI QIDQ2536784
Pierre Cartier, Foata, Dominique
Publication date: 1969
Published in: Lecture Notes in Mathematics (Search for Journal in Brave)
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Permutations, words, matrices (05A05)
Related Items
Square-free words on partially commutative free monoids ⋮ Two oiseau decompositions of permutations and their application to Eulerian calculus ⋮ Contraction of Dirac matrices via chord diagrams ⋮ On some equations in free partially commutative monoids ⋮ A combinatorial approach to matrix algebra ⋮ A decision procedure on partially commutative free monoids ⋮ Clique polynomials have a unique root of smallest modulus ⋮ Algebraic properties of Manin matrices. I ⋮ Infinite traces and symbolic dynamics ⋮ Semi-commutations ⋮ On regular trace languages ⋮ Bijective proofs of basic hypergeometric series identities ⋮ Mixed product and asynchronous automata ⋮ A \(q\)-Foata proof of the \(q\)-Saalschütz identity ⋮ Mixtures of classical and free independence ⋮ A formula for iterated derivatives along trajectories of nonlinear systems ⋮ Theory of traces ⋮ On lexicographic semi-commutations ⋮ Relations between connected and self-avoiding hikes in labelled complete digraphs ⋮ On recognizable subsets of free partially commutative monoids ⋮ A new proof of the Garoufalidis-Lê-Zeilberger quantum MacMahon master theorem ⋮ Théorèmes de transfert pour les polynômes partiellement commutatifs. (Transfer theorems for partially commutative polynomials) ⋮ Applications of the theory of automata in enumeration ⋮ Algebraic and multiple integral identities ⋮ Concurrency and atomicity ⋮ Counting acyclic digraphs by sources and sinks ⋮ Specializations and extensions of the quantum MacMahon master theorem ⋮ Möbius inversion formula for monoids with zero. ⋮ Graph algebras ⋮ The combinatorial interpretation of the Jacobi identity from Lie algebras ⋮ Dependence polynomials of some graph operations ⋮ Homology of certain algebras defined by graphs ⋮ An algebraic theory of sequence enumeration ⋮ Categories de Möbius et fonctorialites: un cadre général pour l'inversion de Möbius ⋮ A dynamical model of parallel computation on bi-infinite time-scale ⋮ The enumeration of sequences with respect to structures on a bipartition ⋮ Combinatorial topology and the global dimension of algebras arising in combinatorics ⋮ Non-repetitive words relative to a rewriting system ⋮ Graph products of spheres, associative graded algebras and Hilbert series. ⋮ Hopf algebras and identities in free partially commutative monoids ⋮ Expansion formulas. I: A general method ⋮ An exact sequence for rings of polynomials in partly commuting indeterminates ⋮ Chain algebras ⋮ A fast algorithm for proving terminating hypergeometric identities ⋮ Un modèle asynchrone pour les systèmes distribués. (An asynchronous model of distributed systems) ⋮ Word problems over traces which are solvable in linear time ⋮ Random ballistic growth and diffusion in symmetric spaces ⋮ Mind the gap: expanding communication options in decentralized discrete-event control ⋮ Algebraic methods for permutations with prescribed patterns ⋮ Une théorie combinatoire des séries formelles ⋮ A combinatorial proof of Dyson's conjecture ⋮ Modelling concurrency with comtraces and generalized comtraces ⋮ Graph monoids ⋮ Fixed points of endomorphisms of trace monoids. ⋮ Un modèle symétrique pour l'identité de Al-Salam-Fields. (A symmetric model for the identity of Al-Salam-Fields) ⋮ Extension of Brzozowski's derivation calculus of rational expressions to series over the free partially commutative monoids ⋮ The geometry of tensor calculus. I ⋮ The enumeration of maximally clustered permutations ⋮ Recognizable closures and submonoids of free partially commutative monoids ⋮ The Poisson-Furstenberg boundary of the locally free group ⋮ The symbiotic relationship of combinatorics and matrix theory ⋮ Growth rates of geometric grid classes of permutations ⋮ Event structures and trace monoids ⋮ Uniform and Bernoulli measures on the boundary of trace monoids ⋮ Generalized semigroup semirings which are zero-divisor-free or multiplicatively left-cancellative ⋮ The active bijection for graphs ⋮ On some decision problems for trace codings ⋮ Logical definability on infinite traces ⋮ Uniform measures on braid monoids and dual braid monoids ⋮ Two recognizable string-matching problems over free partially commutative monoids ⋮ New Euler-Mahonian statistics on permutations and words ⋮ \(\mathbb{N}\)-rationality of zeta functions ⋮ Möbius functions and confluent semi-commutations ⋮ Groups assembled from free and direct products ⋮ Zero loci of skew-growth functions for dual Artin monoids ⋮ Animaux et arbres guingois. (Animals and guingois trees) ⋮ Lyndon bases of free partially commutative Lie algebras ⋮ The poset of infinitary traces ⋮ Partition and composition matrices ⋮ Characteristic polynomials of nonnegative real square matrices and generalized clique polynomials ⋮ The enumeration of fully commutative affine permutations ⋮ A remark on the representation of trace monoids ⋮ Decomposition spaces, incidence algebras and Möbius inversion. III: The decomposition space of Möbius intervals ⋮ Local testability from words to traces, a suitable definition ⋮ Möbius monoids and their connection to inverse monoids. ⋮ Leading coefficients of Kazhdan-Lusztig polynomials for Deodhar elements. ⋮ A noncommutative version of the matrix inversion formula ⋮ Average site perimeter of directed animals on the two-dimensional lattices ⋮ Using transition set sequences to partition behaviors of Petri nets ⋮ Factors of binomial sums from the Catalan triangle ⋮ On universal equivalence of partially commutative Lie algebras defined by graphs without triangles and squares and with no isolated vertices ⋮ A combinatorial proof of the Cayley-Hamilton theorem ⋮ Higher dimensional recursive matrices and diagonal delta sets of series ⋮ A proof of Andrews' \(q\)-Dyson conjecture ⋮ Partial commutations and faithful rational transductions ⋮ Short proofs of Saalschütz's and Dixon's theorems ⋮ Graphs and free partially commutative monoids ⋮ A direct combinatorial proof of a positivity result ⋮ Integrité des algèbres de séries formelles sur un alphabet partiellement commutatif ⋮ A bijective proof of the q-Saalschütz theorem ⋮ Algebraic Combinatorics on Trace Monoids: Extending Number Theory to Walks on Graphs ⋮ The Subtrace Order and Counting First-Order Logic ⋮ On the structure of recognizable languages of dependence graphs ⋮ Preprojective roots and graph monoids of Coxeter groups ⋮ A PRESENTATION FOR THE SYMPLECTIC BLOB ALGEBRA ⋮ Introduction to Probabilistic Concurrent Systems ⋮ Pattern matching in trace monoids ⋮ LAZARD'S ELIMINATION (IN TRACES) IS FINITE-STATE RECOGNIZABLE ⋮ Interview with Igor Pak ⋮ Geometry and Combinatorics via Right-Angled Artin Groups ⋮ Efficient rewriting in cograph trace monoids ⋮ Transformations of sequential specifications into concurrent specifications by synchronization guards ⋮ Mal’tsev bases for partially commutative nilpotent groups ⋮ Cell complexes, poset topology and the representation theory of algebras arising in algebraic combinatorics and discrete geometry ⋮ Efficient solution of some problems in free partially commutative monoids ⋮ Combinatorics of the \(z^{AB}\) theorem ⋮ Dependence polynomials ⋮ From steady-state TASEP model with open boundaries to 1D Ising model at negative fugacity ⋮ Kazhdan-Lusztig polynomials for maximally-clustered hexagon-avoiding permutations. ⋮ Counting walks by their last erased self-avoiding polygons using sieves ⋮ Complete subgraphs of bipartite graphs and applications to trace languages ⋮ Unnamed Item ⋮ Uniform Generation in Trace Monoids ⋮ Semi-trace morphisms and rational transductions ⋮ Some trace monoids where both the Star problem and the Finite Power Property Problem are decidable ⋮ Notes on finite asynchronous automata ⋮ A combinatorial proof of Aldous–Broder theorem for general Markov chains ⋮ Bijective combinatorics of positive braids ⋮ Friends and strangers walking on graphs ⋮ Interview with Xavier Viennot ⋮ A new algorithm for compression of partially commutative alphabets ⋮ Centralizers in graph products of semigroups ⋮ Almost triangular Markov chains on \(\mathbb{N}\) ⋮ Plethysms and operads ⋮ On graph products of monoids ⋮ Modelling Concurrency with Quotient Monoids ⋮ Realizable cycle structures in digraphs ⋮ Independence polynomials and hypergeometric series ⋮ Quantum groups with partial commutation relations ⋮ Probabilistic asynchronous automata ⋮ A survey on automata with translucent letters ⋮ State-deterministic Finite Automata with Translucent Letters and Finite Automata with Nondeterministically Translucent Letters ⋮ Some recent advances in random walks and random environments ⋮ Finite canonical rewriting systems for congruences generated by concurrency relations ⋮ WORD EQUATIONS OVER GRAPH PRODUCTS ⋮ Equilibrium states and growth of quasi-lattice ordered monoids ⋮ APPROXIMATING THE MEAN SPEEDUP IN TRACE MONOIDS ⋮ On the complementation of Büchi asynchronous cellular automata ⋮ Pfaff-Saalschütz revisited ⋮ On the number of partially abelian square-free words on a three-letter alphabet ⋮ Agent-Based Modeling, Mathematical Formalism for ⋮ Note on the Smallest Root of the Independence Polynomial ⋮ Differential (Monoid) Algebra and More ⋮ Computing the closure of sets of words under partial commutations ⋮ Compositions de fonctions de commutation partielle ⋮ A combinatorial formula for the linearization coefficients of general Sheffer polynomials ⋮ Approximability and Non-approximability Results in Computing the Mean Speedup of Trace Monoids ⋮ Entropy and the clique polynomial ⋮ Partially abelian squarefree words ⋮ A fast algorithm for proving terminating hypergeometric identities. (Reprint) ⋮ On the Bessel functions ⋮ Acyclic orientations and the chromatic polynomial ⋮ A new decomposition of derangements ⋮ Toric partial orders ⋮ On the multigraded Hilbert and Poincaré-Betti series and the Golod property of monomial rings ⋮ Extension of MacMahon's master theorem to pre-semi-rings ⋮ Special issue in honor of Dominique Foata's 65th birthday. Proceedings of the international conference on classical combinatorics (FoataFest), Temple University, Philadelphia, PA, USA, June 2000 ⋮ Classical combinatorics: Special issue in honor of Dominique Foata ⋮ Counting domino tilings of rectangles via resultants ⋮ A generalization of traces ⋮ Finite transducers for divisibility monoids ⋮ Trace monoids with idempotent generators and measure-only quantum automata ⋮ Inequivalent factorizations of permutations ⋮ Symbolic Dynamics, Flower Automata and Infinite Traces ⋮ Relations between cumulants in noncommutative probability ⋮ ON ASYNCHRONOUS CELLULAR AUTOMATA ⋮ Unnamed Item ⋮ Faà di Bruno for operads and internal algebras ⋮ Word problems over traces which are solvable in linear time ⋮ A Formal Calculus for the Enumerative System of Sequences-I. Combinatorial Theorems ⋮ Friends and strangers walking on graphs ⋮ LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE ⋮ Characterizations of the decidability of some problems for regular trace languages ⋮ Algebraic Structure of Step Traces and Interval Traces ⋮ The nature of generalized scales ⋮ On the synchronization of traces ⋮ CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store ⋮ On the automaticity of singular Artin monoids of finite type ⋮ SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE ⋮ On the average Cartier-Foata height of traces ⋮ A Combinatorial Proof of Bass’s Evaluations of the Ihara-Selberg Zeta Function for Graphs ⋮ Surface Subgroups of Graph Groups ⋮ Graph groups are biautomatic ⋮ Combinatorial objects enumerated by \(q\)-Bessel functions ⋮ Asynchronous automata versus asynchronous cellular automata ⋮ Lyndon traces and shuffle algebras ⋮ The proof of Birman's conjecture on singular braid monoids. ⋮ Two optimal parallel algorithms on the commutation class of a word ⋮ Deterministic asynchronous automata for infinite traces ⋮ Two techniques in the area of the star problem in trace monoids ⋮ Undecidability of the trace coding problem and some decidable cases ⋮ Algorithmic problems in right-angled Artin groups: complexity and applications ⋮ Incidence Hopf algebras ⋮ Theorems for a price: Tomorrow's semi-rigorous mathematical culture ⋮ The death of proof? Semi-rigorous mathematics? You've got to be kidding! ⋮ 321-avoiding affine permutations and their many heaps ⋮ Interpretation of a basic hypergeometric identity with Lie characters and Young tableaux ⋮ Binomial identities -- combinatorial and algorithmic aspects ⋮ The Euler-Mahonian distributions over the words ⋮ A note on Möbius functions of upho posets ⋮ On the complementation of asynchronous cellular Büchi automata ⋮ Modular Hecke algebras over Möbius categories ⋮ Honda sequences ⋮ Lyndon heaps: An analogue of Lyndon words in free partially commutative monoids ⋮ Decomposition spaces, incidence algebras and Möbius inversion. I: Basic theory ⋮ Diagram calculus for a type affine \(C\) Temperley-Lieb algebra. II. ⋮ The Hafnian master theorem ⋮ Markovian dynamics of concurrent systems ⋮ Recursive statistics on words ⋮ The code problem for traces -- improving the boundaries ⋮ On the dimension of graded algebras ⋮ Toward uniform random generation in 1-safe Petri nets ⋮ Universal equivalence of partially commutative Lie algebras ⋮ A cut-invariant law of large numbers for random heaps ⋮ Mask formulas for cograssmannian Kazhdan-Lusztig polynomials. ⋮ Universal equivalence of partially commutative metabelian Lie algebras ⋮ The Tutte-Grothendieck group of an alphabetic rewriting system ⋮ Inversion formula for the growth function of a cancellative monoid. ⋮ A Hopf algebra for counting cycles ⋮ Computing the average parallelism in trace monoids. ⋮ Major index for 01-fillings of moon polyominoes ⋮ Solving word equations modulo partial commutations ⋮ Folded Hasse diagrams of combined traces ⋮ The word problem for \(1\mathcal{LC}\) congruences is NP-hard. ⋮ The topology of Mazurkiewicz traces. ⋮ Asymptotic combinatorics of Artin-Tits monoids and of some other monoids ⋮ Non-commutative extensions of the MacMahon Master Theorem ⋮ Combinatorics of sequential dynamical systems ⋮ Incidence bicomodules, Möbius inversion and a Rota formula for infinity adjunctions ⋮ Empilements de segments et \(q\)-énumération de polyominos convexes dirigés. (Heaps of segments and \(q\)-enumeration of directed convex polyominoes) ⋮ Star-free trace languages ⋮ Geometry of convex cones and application to the Euclidean projection on the positive Weyl chamber ⋮ Semicommutations and algebraic languages ⋮ The free partially commutative Lie algebra: Bases and ranks ⋮ Quivers, words and fundamentals ⋮ Decidability of the star problem in \(A^*\times{}\{ b\}^*\) ⋮ The lower central series of the free partially commutative group ⋮ String matching problems over free partially commutative monoids ⋮ Möbius inversion formula for the trace group ⋮ Fully commutative elements in the Weyl and affine Weyl groups. ⋮ Identities in combinatorics. I: On sorting two ordered sets ⋮ Universal enveloping Lie Rota-Baxter algebras of pre-Lie and post-Lie algebras ⋮ On monoids presented by a single relation ⋮ Recognizable subsets of some partially Abelian monoids ⋮ Synchronization of Bernoulli sequences on shared letters ⋮ The incidence comodule bialgebra of the Baez-Dolan construction ⋮ A proof of Andrews' \(q\)-Dyson conjecture. (Reprint) ⋮ Quasideterminants ⋮ Length enumeration of fully commutative elements in finite and affine Coxeter groups ⋮ The unification of certain enumeration problems for sequences ⋮ Right angled Artin groups and partial commutation, old and new ⋮ A spectral property for concurrent systems and some probabilistic applications ⋮ Hopf algebra structure of generalized quasi-symmetric functions in partially commutative variables ⋮ Whitney numbers for poset cones ⋮ Operational semantics with semicommutations ⋮ The shuffle algebra and its derivations ⋮ Möbius functions of directed restriction species and free operads, via the generalised Rota formula ⋮ On the Knuth-Bendix completion for concurrent processes ⋮ An umbral relation between pattern and commutation in strings ⋮ A non-commutative version of Jacobi's equality on the cofactors of a matrix ⋮ The lattices of prefixes and overlaps of traces ⋮ On the fully commutative elements of Coxeter groups ⋮ A weak order approach to group ranking ⋮ Acyclic orientations of random graphs ⋮ A coupling of the spectral measures at a vertex ⋮ Membership problems for regular and context-free trace languages ⋮ Concurrency measure in commutation monoids ⋮ Upper estimate of the cardinality of the set of knots generated by one- and two-dimensional braids ⋮ Acyclic heaps of pieces. I. ⋮ Elements of a theory of computer simulation. I ⋮ Determinants and Möbius functions in trace monoids ⋮ Flag-symmetry of the poset of shuffles and a local action of the symmetric group ⋮ The star problem and the finite power property in trace monoids: Reductions beyond C4 ⋮ Partially commutative Artin-Coxeter groups and their arboreal structure. ⋮ Atomic semicommutations ⋮ Number of prefixes in trace monoids: clique polynomials and dependency graphs ⋮ \(q\)-enumeration of convex polyominoes ⋮ An extension of Kleene's and Ochmański's theorems to infinite traces ⋮ On the support of graph Lie algebras ⋮ A theory of noncommutative determinants and characteristic functions of graphs ⋮ Recognizable trace languages, distributed automata and the distribution problem ⋮ Deterministic concurrent systems
