Showing 2008Show all
2 papers · 1 filter
quant-ph2008
An application of the Deutsch-Josza algorithm to formal languages and the word problem in groups
Michael Batty, Andrea Casaccino, Andrew J. Duncan +2
We adapt the Deutsch-Josza algorithm to the context of formal language theory. Specifically, we use the algorithm to distinguish between trivial and nontrivial words in groups give…
math.GR2008
Groups that do and do not have context-sensitive word problem
Derek F. Holt, Sarah Rees, Michael Shapiro
We prove that a group has word problem that is a growing context-sensitive language precisely if its word problem can be solved using a non-deterministic Cannon's algorithm (the de…