RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS

DOI10.1142/S0218196795000185MaRDI QIDQ4852676zbMATH OpenOpenAlexFDO

Authors Pavel Goralčík, Václav Koubek

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

decidable in polynomial timegenerator sequencesidempotent transformations

Mathematics Subject Classification ID

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

Recommendations

• The complexity of properties of transformation semigroups
• Complexity of identity checking in transformation semigroups of rank 2.
• scientific article; zbMATH DE number 4068272
• Identity checking problem for transformation monoids
• Characterization of idempotent transformation monoids

Cited in

(18)

• Algebraic transformation of differential characteristic decompositions from one ranking to another
• Characterization of idempotent transformation monoids
• Ordering D-classes and computing Schein rank is hard
• On automata recognizing birecurrent sets
• Černý's conjecture and the road colouring problem
• Completely reachable automata
• Synchronizing Automata Preserving a Chain of Partial Orders
• Synchronizing Automata and the Černý Conjecture
• scientific article; zbMATH DE number 4068272 (Why is no real title available?)
• Les automates circulaires biaisés vérifient la conjecture de Černý
• The complexity of properties of transformation semigroups
• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
• Rank-one transformations, odometers, and finite factors
• Subset mapping problems in solvable automata
• Monoids of upper triangular matrices over the Boolean semiring
• Parameterized complexity of factorization problems
• Efficiently computing the minimum rank of a matrix in a monoid of zero-one matrices
• Synchronizing automata preserving a chain of partial orders

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

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