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

DOI10.1016/J.TCS.2005.03.026MaRDI QIDQ557909zbMATHOpenAlexFDO

Authors Murray Elder

Publication date 30 June 2005

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

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

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)

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.

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.

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 848082 (Why is no real title available?)
• Groups, the theory of ends, and context-free languages
• Growth Functions for Some Nonautomatic Baumslag-Solitar Groups
• Growth series for the group \(\langle x,y\mid x^{-1}yx=y^ l\rangle\)
• Minimal almost convexity
• Minimal length normal forms for some soluble groups
• On groups whose word problem is solved by a counter automaton.

Cited in

(9)

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

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)