Word problems of groups: formal languages, characterizations and decidability

DOI10.1016/J.TCS.2018.05.007MaRDI QIDQ1623276zbMATH OpenOpenAlexWikidataFDO

Authors Sam A. M. Jones, Richard M. Thomas

Publication date 23 November 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2381/42543

zbMATH Keywords

groupsdecidabilityfinite generationword problemsone-counter languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Recommendations

• Formal languages, word problems of groups and decidability
• scientific article; zbMATH DE number 1283959
• Groups whose word problems are accepted by abelian \(G\)-automata
• Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups
• scientific article; zbMATH DE number 3887910
• An automata theoretic approach to the generalized word problem in graphs of groups.
• The word problem for finitary automaton groups
• On groups whose word problem is solved by a counter automaton.
• scientific article; zbMATH DE number 848082
• Characterizing word problems of groups

Cites work

• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1206942 (Why is no real title available?)
• scientific article; zbMATH DE number 1283959 (Why is no real title available?)
• scientific article; zbMATH DE number 534859 (Why is no real title available?)
• scientific article; zbMATH DE number 706263 (Why is no real title available?)
• scientific article; zbMATH DE number 2133330 (Why is no real title available?)
• scientific article; zbMATH DE number 848082 (Why is no real title available?)
• scientific article; zbMATH DE number 3381862 (Why is no real title available?)
• A course in formal languages, automata and groups
• Algebraic Theory of Automata and Languages
• Eine neue Invariante für kontextfreie Sprachen
• Formal languages and group theory
• GROUPS AND SEMIGROUPS WITH A ONE-COUNTER WORD PROBLEM
• GROUPS WITH CONTEXT-FREE REDUCED WORD PROBLEM
• Group presentations, formal languages and characterizations of one- counter groups
• Groups and NTS languages
• Groups, languages and automata
• Groups, the theory of ends, and context-free languages
• Hotz-isomorphism theorems in formal language theory
• On a subclass of context-free groups
• On semigroup presentations
• On the Hotz group of a context-free grammar
• Ordering by Divisibility in Abstract Algebras
• Petri nets and regular languages
• Restricted one-counter machines with undecidable universe problems
• Some Remarks on Semigroup Presentations
• Space complexity and word problems of groups
• Syntactic monoids and word problems.
• The accessibility of finitely presented groups
• The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages
• The theory of ends, pushdown automata, and second-order logic
• \(L(A)=L(B)\)? decidability results from complete formal systems

Cited in

(16)

• Groups whose word problem is a Petri net language
• Solving word problems in group extensions over infinite words
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
• scientific article; zbMATH DE number 2221698 (Why is no real title available?)
• scientific article; zbMATH DE number 7204548 (Why is no real title available?)
• On groups whose word problem is solved by a counter automaton.
• ON REAL-TIME WORD PROBLEMS
• Word problems recognisable by deterministic blind monoid automata
• Analytical reconstruction formula with efficient implementation for a modality of Compton scattering tomography with translational geometry
• scientific article; zbMATH DE number 871439 (Why is no real title available?)
• scientific article; zbMATH DE number 3887910 (Why is no real title available?)
• scientific article; zbMATH DE number 5785814 (Why is no real title available?)
• The use of Knuth-Bendix methods to solve the word problem in automatic groups
• Characterizing word problems of groups
• Prefix-free languages, simple grammars representing a group element, languages of partial order in a group
• Formal languages, word problems of groups and decidability

This page was built for publication: Word problems of groups: formal languages, characterizations and decidability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1623276)