2021 | OriginalPaper | Chapter
On the Computational Power of Programs over \(\mathsf {BA}_2\) Monoid
Authors : Manasi S. Kulkarni, Jayalal Sarma, Janani Sundaresan
Published in: Language and Automata Theory and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
-
If a program over \(\mathsf {BA}_2\) is non-nullable, then there is an equivalent program with length at most \({\mathsf {poly}}(n)\).
-
If a program over \(\mathsf {BA}_2\) is nullable, then it should be exponentially non-nullable - that is there should be at least \(2^{\varOmega (n)}\) many inputs which send the output of the program to 0 of \(\mathsf {BA}_2\). We show that for any program P over \(\mathsf {BA}_2\), if the zeroes of the program have a witness subprogram of polynomial length, then there is a program of length \({\mathsf {poly}}(n)\) equivalent to program P.