The Complexity of Verbal Languages over Groups

DOI10.1109/LICS.2012.50zbMath1361.68122OpenAlexW1975987235MaRDI QIDQ2986816

Sanjay Jain, Frank Stephan, Alexei G. Myasnikov

Publication date: 16 May 2017

Published in: 2012 27th Annual IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/lics.2012.50

zbMATH Keywords

free groupsChomsky hierarchyverbal languagesThurston automatic groups

Mathematics Subject Classification ID

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

Related Items

On asymptotic properties of verbal subsets in a group. ⋮ The complexity of solution sets to equations in hyperbolic groups ⋮ Ambiguity of Morphisms in a Free Group ⋮ Solution Sets for Equations over Free Groups are EDT0L Languages ⋮ Learning pattern languages over groups ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ Applications of L systems to group theory ⋮ Unambiguous injective morphisms in free groups