On the computational power of programs over \(\mathsf{BA}_2\) monoid

DOI10.1007/978-3-030-68195-1_3OpenAlexW3130993066MaRDI QIDQ2232262

Manasi S. Kulkarni, Janani Sundaresan, M. N. Jayalal Sarma

Publication date: 4 October 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-68195-1_3

zbMATH Keywords

combinatorics on wordsmonoids and computationpolynomial length program (PLP) conjectureprograms over monoids

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(NC^ 1\): The automata-theoretic viewpoint
• Non-uniform automata over groups
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Finite semigroup varieties defined by programs
• Programs over semigroups of dot-depth one
• Finite monoids and the fine structure of NC ¹
• The membership problem in aperiodic transformation monoids
• The Power of Programs over Monoids in DA
• A Property of Finite Simple Non-Abelian Groups
• Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines

This page was built for publication: On the computational power of programs over \(\mathsf{BA}_2\) monoid