The membership problem in aperiodic transformation monoids

DOI10.1145/146637.146661zbMath0803.20046OpenAlexW2111132083MaRDI QIDQ4302805

Martin Beaudry, Denis Thérien, Pierre McKenzie

Publication date: 5 January 1995

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/146637.146661

zbMATH Keywords

computational complexityvarietiesmembership problemtransformation monoidsfinite aperiodic monoids

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Lattices of varieties (08B15) Varieties and pseudovarieties of semigroups (20M07) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

The complexity of intersecting finite automata having few final states ⋮ Problems on finite automata and the exponential time hypothesis ⋮ The intersection problem for finite monoids ⋮ Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic ⋮ Deciding FO-definability of regular languages ⋮ On the computational power of programs over \(\mathsf{BA}_2\) monoid ⋮ Two-letter group codes that preserve aperiodicity of inverse finite automata. ⋮ Learning expressions and programs over monoids ⋮ Unnamed Item ⋮ Languages recognized by finite aperiodic groupoids ⋮ Problems on Finite Automata and the Exponential Time Hypothesis ⋮ The Intersection Problem for Finite Semigroups

This page was built for publication: The membership problem in aperiodic transformation monoids