RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS

DOI10.1142/S0218196795000185zbMath0831.20089OpenAlexW1995717557MaRDI QIDQ4852676

Václav Koubek, Pavel Goralčík

Publication date: 26 November 1995

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218196795000185

zbMATH Keywords

idempotent transformationsgenerator sequencesdecidable in polynomial time

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Free semigroups, generators and relations, word problems (20M05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

On automata recognizing birecurrent sets ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Synchronizing automata preserving a chain of partial orders ⋮ Approximating the minimum length of synchronizing words is hard ⋮ Synchronizing Automata Preserving a Chain of Partial Orders ⋮ Les automates circulaires biaisés vérifient la conjecture de Černý ⋮ Synchronizing Automata and the Černý Conjecture ⋮ Completely Reachable Automata ⋮ Černý's conjecture and the road colouring problem

This page was built for publication: RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS