Holt, Derek F., Rees, Sarah, Röver, Claas E. and Thomas, Richard M.. (2005) Groups with context-free co-word problem. Journal of the London Mathematical Society, Vol.71 (No.3). pp. 643-657. ISSN 0024-6107

Preview

PDF WRAP_Holt_Context_free_co-word.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (225Kb)

Abstract

The class of co-context-free groups is studied. A co-context-free group is defined as one whose coword problem (the complement of its word problem) is context-free. This class is larger than the subclass of context-free groups, being closed under the taking of finite direct products, restricted standard wreath products with context-free top groups, and passing to finitely generated subgroups and finite index overgroups. No other examples of co-context-free groups are known. It is proved that the only examples amongst polycyclic groups or the Baumslag–Solitar groups are virtually abelian. This is done by proving that languages with certain purely arithmetical properties cannot be context-free; this result may be of independent interest.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH):	Word problems (Mathematics), Group theory, Programming languages (Electronic computers), Polycyclic groups
Journal or Publication Title:	Journal of the London Mathematical Society
Publisher:	Cambridge University Press
ISSN:	0024-6107
Date:	June 2005
Volume:	Vol.71
Number:	No.3
Page Range:	pp. 643-657
Identification Number:	10.1112/S002461070500654X
Status:	Peer Reviewed
Access rights to Published version:	Open Access
Funder:	Engineering and Physical Sciences Research Council (EPSRC)
References:	1. V. A. Anisimov, ‘The group languages’, Kibernetika 4 (1971) 18–24. 2. R. Beigel and R. W. Floyd, The language of machines: an introduction to computability and formal languages (Computer Science Press, New York, 1994). 3. M. Dunwoody, ‘The accessibility of finitely presented groups’, Invent. Math. 81 (1985) 449–457. 4. S. Ginsburg, The mathematical theory of context-free languages (McGraw–Hill, New York, 1966). 5. T. Herbst, ‘On a subclass of context-free groups’, RAIRO Inform. Théor. Appl. 25 (1991) 255–272. 6. D. F. Holt and C. E. Röver, ‘Groups with indexed co-word problem’, Preprint, 2004. 7. J. E. Hopcroft and J. D. Ullman, Introduction to automata theory, languages, and computation (Addison–Wesley, Reading, MA, 1979). 8. A. Karrass, W. Magnus and D. Solitar, Combinatorial group theory (Dover, New York, 1976). 9. C. F. Miller III, ‘On group-theoretic decision problems and their classification’, Annals of Mathematics Studies 68 (Princeton University Press, Princeton, NJ, 1971). 10. C. F. Miller III, ‘Decision problems for groups – survey and reflection’, Algorithms and classification in combinatorial group theory (ed. G. Baumslag and C. F. Miller III, Springer, 1992) 1–60. 11. D. E. Muller and P. E. Schupp, ‘Groups, the theory of ends, and context-free languages’, J. Comput. System Sci. 26 (1983) 295–310. 12. D. E. Muller and P. E. Schupp, ‘The theory of ends, pushdown automata, and second-order logic’, Theoret. Comput. Sci. 37 (1985) 51–75. 13. R. J. Parikh, ‘Language generating devices’, MIT Res. Lab. Electron. Quart. Prog. Rep. 60 (1961) 199–212. 14. D. W. Parkes and R. M. Thomas, ‘Syntactic monoids and word problems’, Arab. J. Sci. Engrg. 25 (2000) 81–94. 15. D. J. S. Robinson, A course in the theory of groups (Springer, New York, 1993). 16. I. N. Stewart and D. O. Tall, Algebraic number theory, 2nd edn (Chapman & Hall, London, 1987).
URI:	http://wrap.warwick.ac.uk/id/eprint/746

Request changes to a record

Actions (login required)

View Item