A context-free and a 1-counter geodesic language for a Baumslag-Solitar group

DOI10.1016/J.TCS.2005.03.026zbMATH Open1142.68041arXivmath/0411166OpenAlexW2043281883MaRDI QIDQ557909FDOQ557909

Authors: Murray Elder 

Publication date: 30 June 2005

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

Abstract: We give a language of unique geodesic normal forms for the Baumslag-Solitar group BS(1,2) that is context-free and 1-counter. We discuss the classes of context-free, 1-counter and counter languages, and explain how they are inter-related.

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

Recommendations

• A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.
• A new proof of the growth rate of the solvable Baumslag-Solitar groups
• Growth in Baumslag-Solitar groups. II: The Bass-Serre tree
• Growth in Baumslag-Solitar groups. I: Subgroups and rationality.
• On computing geodesics in Baumslag-Solitar groups.

zbMATH Keywords

regular languagecontext-free languageBaumslag-Solitar group\(G\)-automaton1-counter languagecounter languagelanguage of geodesics

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On groups whose word problem is solved by a counter automaton.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Groups, the theory of ends, and context-free languages
• Minimal almost convexity
• Growth series for the group \(\langle x,y\mid x^{-1}yx=y^ l\rangle\)
• Growth Functions for Some Nonautomatic Baumslag-Solitar Groups
• Title not available (Why is that?)
• Minimal length normal forms for some soluble groups

Cited In (7)

• Thompson's group \(F\) is 1-counter graph automatic.
• Limits of Baumslag-Solitar groups and dimension estimates in the space of marked groups.
• Markov semigroups, monoids and groups.
• Cone types and geodesic languages for lamplighter groups and Thompson's group \(F\).
• Groups whose word problems are not semilinear
• On computing geodesics in Baumslag-Solitar groups.
• Metric properties of Baumslag–Solitar groups

This page was built for publication: A context-free and a 1-counter geodesic language for a Baumslag-Solitar group

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