A NOTE ON CONTEXT-SENSITIVE LANGUAGES AND WORD PROBLEMS

DOI10.1142/S0218196794000129zbMath0832.20052arXivmath/9306204OpenAlexW1995352162MaRDI QIDQ4697866

Michael Shapiro

Publication date: 22 February 1996

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/9306204

zbMATH Keywords

finitely generated subgroupsautomatic groupscontext-sensitive languagescontext- sensitive word problemdeterministic linear bounded automatashort asynchronous combings

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Geometric group theory (20F65) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)

Related Items (8)

WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM ⋮ Geodesic growth in virtually abelian groups ⋮ On the complexity of the cogrowth sequence ⋮ \(\mathcal C\)-graph automatic groups. ⋮ Context-sensitive languages and G-automata ⋮ ON A GENERALIZATION OF DEHN'S ALGORITHM ⋮ GROUPS THAT DO AND DO NOT HAVE GROWING CONTEXT-SENSITIVE WORD PROBLEM ⋮ Automatic semigroups

This page was built for publication: A NOTE ON CONTEXT-SENSITIVE LANGUAGES AND WORD PROBLEMS