arxiv: 2604.22375 · v1 · submitted 2026-04-24 · 🧮 math.GR · cs.FL

Recognition: unknown

Visibly Pushdown Languages in Groups

Daniel Turaev, Laura Ciobanu

Pith reviewed 2026-05-08 09:03 UTC · model grok-4.3

classification 🧮 math.GR cs.FL

keywords visibly pushdown languagesword problemfinitely generated groupsrecognisable setsfree reductionundecidabilityfree groups

0 comments

The pith

The word problem of a finitely generated group is a visibly pushdown language precisely when the group is finite.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines how visibly pushdown languages connect to the word problems and other natural sets of words in finitely generated groups. It proves that the word problem belongs to this language class exactly when the group is finite. The authors further show that free reduction does not preserve membership in visibly pushdown languages and that solving equations in free groups with constraints requiring reduced words from such a language is undecidable. They analyze sets whose full preimages are visibly pushdown and find these sets are often recognisable, while conjecturing that the classes coincide exactly in every group.

Core claim

The authors establish that the word problem of a finitely generated group is a visibly pushdown language if and only if the group is finite. They prove that free reduction does not preserve the visibly pushdown property. The problem of finding solutions to equations in a free group, where the solutions must be reduced words belonging to a visibly pushdown language, is undecidable. Sets with visibly pushdown full preimages are frequently recognisable sets, and the authors conjecture that this class equals the recognisable sets in any group.

What carries the argument

The word problem language of the group over a finite generating set, and its membership in the class of visibly pushdown languages.

If this is right

The word problem of a group is visibly pushdown exactly when the group is finite.
Free reduction of words does not preserve membership in visibly pushdown languages.
Solving equations in free groups subject to visibly pushdown constraints on the reduced words is undecidable.
Sets whose full preimages are visibly pushdown are often recognisable sets.
In any group the class of sets with visibly pushdown preimages may coincide with the recognisable sets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Visibly pushdown automata cannot recognize the word problems of any infinite finitely generated group.
This limits the use of stack automata with visible operations for deciding equality to the identity in infinite groups.
Analogous results may hold when replacing visibly pushdown languages with other classes such as deterministic context-free languages.
A proof of the conjecture would give a complete algebraic description of the sets reachable via visibly pushdown preimages in groups.

Load-bearing premise

The standard definitions of visibly pushdown languages and the word problem extend without modification to all finitely generated groups, and the equivalence and undecidability proofs hold in full generality.

What would settle it

An infinite finitely generated group whose word problem is a visibly pushdown language for some finite generating set would disprove the central equivalence.

Figures

Figures reproduced from arXiv: 2604.22375 by Daniel Turaev, Laura Ciobanu.

**Figure 1.** Figure 1: Thus π(L) ⊂ F2 is a VPL∃ set. However, the set of reduced words r(L) = {a nb 2n | n ∈ N} is not VPL for any partition of the alphabet. Indeed, consider the infinite family {a nb n | n ∈ N}. Each pair of words a i b i and a j b j for i ̸= j in this family can be pairwise distinguished from one another by the suffix b j . If b is not a response, then b j ∈ MR for every j. Thus the congruence ≡ is infinite in… view at source ↗

read the original abstract

In this paper we explore the connections between the class of Visibly Pushdown Languages ($\mathbf{VPL}$) and the natural sets of words one can associate to a finitely generated group. We show that the word problem of a finitely generated group is $\mathbf{VPL}$ exactly when the group is finite. We also show that free reduction does not preserve $\mathbf{VPL}$, and that finding solutions to equations in a free group with $\mathbf{VPL}$ constraints (as reduced words) is undecidable. We explore the structure of sets whose full preimage is $\mathbf{VPL}$, showing these are often recognisable sets. We conjecture that, in any group, this class is precisely the recognisable sets.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper shows the word problem is VPL exactly for finite groups, plus undecidability for constrained equations in free groups and a conjecture on recognizable sets.

read the letter

The main thing to know is that this paper shows the word problem of a finitely generated group is visibly pushdown exactly when the group is finite. It also proves that free reduction does not preserve VPL and that VPL-constrained equations in free groups are undecidable. They conjecture that sets with VPL preimages are precisely the recognizable ones. This equivalence is new in this form. It uses the stricter stack discipline of VPL compared to general context-free languages. For groups like Z the word problem is not context-free, so certainly not VPL. For free groups the word problem is context-free but the PDA requires looking at the stack top, violating visibility. The non-preservation under free reduction is a useful negative result since reduction is central to group computations. The undecidability follows from encoding problems that VPL cannot handle. The conjecture organizes the positive cases. The paper does well by giving a clean if-and-only-if statement for finite groups and by linking to recognizable sets, which are well-studied in group theory. The results are presented directly without unnecessary machinery. The soft spots are minor. The proofs likely rely on standard constructions, but one should verify how they manage the visibility for arbitrary generating sets and whether the undecidability proof covers all cases of VPL constraints. The conjecture lacks supporting theorems beyond the exploration mentioned, so it remains open. No internal contradictions or fitting issues show up. This work suits readers in computational group theory who care about language-theoretic restrictions on word problems. It could help design algorithms by ruling out VPL approaches for infinite groups. It deserves peer review because the claims are concrete, the reasoning aligns with automata distinctions, and the conjecture invites further study. I recommend sending this for peer review. The evidence aligns with known facts and makes the work worth a full referee report.

Referee Report

0 major / 2 minor

Summary. The paper explores connections between visibly pushdown languages (VPL) and natural word sets in finitely generated groups. It proves that the word problem of a finitely generated group is VPL exactly when the group is finite. It shows that free reduction does not preserve VPL, proves undecidability of solving equations in free groups with VPL constraints on reduced words, examines sets whose full preimages are VPL (showing they are often recognizable), and conjectures that this class coincides with the recognizable sets in any group.

Significance. If the results hold, the work supplies a sharp characterization separating VPL from context-free languages for group word problems, consistent with the stricter visibility constraint on stack operations. The undecidability result for VPL-constrained equations in free groups is a concrete algorithmic limitation. The conjecture on recognizable sets offers a potential unifying perspective. The derivations rely on standard definitions of VPL and group word problems without ad-hoc parameters or invented entities.

minor comments (2)

[Introduction] The introduction would benefit from a concise recall of the definition of visibly pushdown automata and the visibility condition on stack operations, to aid readers primarily from group theory.
[Undecidability section] In the undecidability section, the reduction from a known undecidable problem (such as the word problem in free groups or Post correspondence) should be stated with an explicit reference to the source result for clarity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for recommending minor revision. The referee summary accurately reflects the main results: the word problem of a finitely generated group is VPL if and only if the group is finite, free reduction does not preserve VPL, equation solving with VPL constraints is undecidable in free groups, and sets with VPL preimages are often recognizable, along with the conjecture that this class coincides with the recognizable sets.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives its central results directly from the standard definitions of visibly pushdown languages and the word problem for finitely generated groups. The equivalence (word problem is VPL exactly when the group is finite) follows from automata-theoretic distinctions between VPL and other classes such as CFL, without any self-referential constructions, fitted parameters renamed as predictions, or load-bearing self-citations. The claims that free reduction does not preserve VPL and that VPL-constrained equations in free groups are undecidable are obtained from known properties of pushdown automata and group presentations. The exploration of preimages and the conjecture about recognizable sets are presented as open or derived observations rather than forced by prior inputs. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on established definitions from automata theory and group theory without introducing new fitted parameters or postulated entities.

axioms (2)

standard math Standard definition of visibly pushdown languages via pushdown automata with visible stack operations.
Invoked to define the class VPL throughout the results.
domain assumption The word problem of a group is the set of words over the generators that represent the identity element.
Central to the first main theorem on when this set is VPL.

pith-pipeline@v0.9.0 · 5406 in / 1433 out tokens · 53932 ms · 2026-05-08T09:03:35.578748+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

32 extracted references · 17 canonical work pages

[1]

In: Automata, languages and programming, Lecture Notes in Comput

Alur, R., Kumar, V., Madhusudan, P., Viswanathan, M.: Congruences for visibly pushdown languages. In: Automata, languages and programming, Lecture Notes in Comput. Sci., vol. 3580, pp. 1102–1114. Springer, Berlin (2005).https://doi. org/10.1007/11523468_89

work page doi:10.1007/11523468_89 2005
[2]

In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing

Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing. pp. 202–211. ACM, New York (2004).https://doi.org/10.1145/1007352.1007390

work page doi:10.1145/1007352.1007390 2004
[3]

In: Developments in language theory, Lecture Notes in Comput

Alur, R., Madhusudan, P.: Adding nesting structure to words. In: Developments in language theory, Lecture Notes in Comput. Sci., vol. 4036, pp. 1–13. Springer, Berlin (2006).https://doi.org/10.1007/11779148_1

work page doi:10.1007/11779148_1 2006
[4]

Kibernetika (Kiev) (4), 18–24 (1971)

Anisimov, A.V.: The group languages. Kibernetika (Kiev) (4), 18–24 (1971)

1971
[5]

Benois, M.: Parties rationnelles du groupe libre. C. R. Acad. Sci. Paris Sér. A-B 269, A1188–A1190 (1969)

1969
[6]

Israel J

Bucher, M., Talambutsa, A.: Exponential growth rates of free and amalgamated products. Israel J. Math.212(2), 521–546 (2016).https://doi.org/10.1007/ s11856-016-1299-4

2016
[7]

Carvalho, A., Nyberg-Brodda, C.F.: On linguistic subsets of groups and monoids (2025),https://arxiv.org/abs/2502.14329

work page arXiv 2025
[8]

In: Developments in language theory, Lecture Notes in Comput

Ciobanu, L.: Word equations, constraints, and formal languages. In: Developments in language theory, Lecture Notes in Comput. Sci., vol. 14791, pp. 1–12. Springer, Cham ([2024]©2024).https://doi.org/10.1007/978-3-031-66159-4_1

work page doi:10.1007/978-3-031-66159-4_1 2024
[9]

Ciobanu, L., Evetts, A., Levine, A.: Effective equation solving, constraints, and growth in virtually abelian groups. SIAM J. Appl. Algebra Geom.9(1), 235–260 (2025).https://doi.org/10.1137/23M1604679

work page doi:10.1137/23m1604679 2025
[10]

International Mathematics Research Notices2024(5), 4119–4159 (03 2024).https://doi.org/ 10.1093/imrn/rnad179

Ciobanu, L., Garreta, A.: Group equations with abelian predicates. International Mathematics Research Notices2024(5), 4119–4159 (03 2024).https://doi.org/ 10.1093/imrn/rnad179

work page doi:10.1093/imrn/rnad179 2024
[11]

Ciobanu, L., Hermiller, S.: Conjugacy growth series and languages in groups. Trans. Amer. Math. Soc.366(5), 2803–2825 (2014).https://doi.org/10.1090/ S0002-9947-2013-06052-7

2014
[12]

Israel J

Ciobanu, L., Hermiller, S., Holt, D., Rees, S.: Conjugacy languages in groups. Israel J. Math.211(1), 311–347 (2016).https://doi.org/10.1007/s11856-015-1274-5 16 L. Ciobanu and D. Turaev

work page doi:10.1007/s11856-015-1274-5 2016
[13]

In: Languages and automata—GAGTA Book 3, pp

Ciobanu, L., Levine, A.: Languages, groups, and equations. In: Languages and automata—GAGTA Book 3, pp. 63–93. De Gruyter, Berlin ([2024]©2024)

2024
[14]

Theory Comput

Day, J., Ganesh, V., Grewal, N., Konefal, M., Manea, F.: A closer look at the expressive power of logics based on word equations. Theory Comput. Syst.68(3), 322–379 (2024).https://doi.org/10.1007/s00224-023-10154-8

work page doi:10.1007/s00224-023-10154-8 2024
[15]

Day, J.D., Ganesh, V., Grewal, N., Manea, F.: On the expressive power of string constraints. Proc. ACM Program. Lang.7(POPL) (Jan 2023).https://doi.org/ 10.1145/3571203

work page doi:10.1145/3571203 2023
[16]

Diekert, V., Gutierrez, C., Hagenah, C.: The existential theory of equations with rational constraints in free groups is PSPACE-complete. Inform. and Comput. 202(2), 105–140 (2005).https://doi.org/10.1016/j.ic.2005.04.002

work page doi:10.1016/j.ic.2005.04.002 2005
[17]

In: Beyersdorff, O., Kanté, M.M., Kupferman, O., Lokshtanov, D

Göller, S., Grosshans, N.: TheAC 0-Complexity of Visibly Pushdown Lan- guages. In: Beyersdorff, O., Kanté, M.M., Kupferman, O., Lokshtanov, D. (eds.) 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 289, pp. 38:1–38:18. Schloss Dagstuhl – Leibniz-Zentrum f...

work page doi:10.4230/lipics.stacs.2024.38 2024
[18]

Grunschlag, Z.: Algorithms in Geometric Group Theory. Ph.D. thesis, University of California at Berkley (1999)

1999
[19]

Henry, C.S.: The (nested) word problem. Inform. Process. Lett.116(11), 729–734 (2016).https://doi.org/10.1016/j.ipl.2016.06.013

work page doi:10.1016/j.ipl.2016.06.013 2016
[20]

RAIRO Inform

Herbst, T.: On a subclass of context-free groups. RAIRO Inform. Théor. Appl. 25(3), 255–272 (1991).https://doi.org/10.1051/ita/1991250302551

work page doi:10.1051/ita/1991250302551 1991
[21]

Theoretical Computer Science112(2), 187–213 (1993).https://doi.org/https://doi.org/10.1016/0304-3975(93)90018-O, https://www.sciencedirect.com/science/article/pii/030439759390018O

Herbst, T., Thomas, R.M.: Group presentations, formal languages and character- izations of one-counter groups. Theoretical Computer Science112(2), 187–213 (1993).https://doi.org/https://doi.org/10.1016/0304-3975(93)90018-O, https://www.sciencedirect.com/science/article/pii/030439759390018O

work page doi:10.1016/0304-3975(93)90018-o 1993
[22]

Groups Complexity Cryptology10(1), 9–15 (2018).https://doi.org/doi:10.1515/ gcc-2018-0003

Ho, M.C.: The word problem ofZn is a multiple context-free language. Groups Complexity Cryptology10(1), 9–15 (2018).https://doi.org/doi:10.1515/ gcc-2018-0003

2018
[23]

Addison-Wesley Series in Computer Science, Addison-Wesley Pub- lishing Co., Reading, MA (1979)

Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Addison-Wesley Series in Computer Science, Addison-Wesley Pub- lishing Co., Reading, MA (1979)

1979
[24]

Journal of Algebra248(2), 608–668 (2002).https://doi.org/https://doi.org/ 10.1006/jabr.2001.9033

Kapovich, I., Myasnikov, A.G.: Stallings foldings and subgroups of free groups. Journal of Algebra248(2), 608–668 (2002).https://doi.org/https://doi.org/ 10.1006/jabr.2001.9033

work page doi:10.1006/jabr.2001.9033 2002
[25]

Groups Complex

Kropholler, R.P., Spriano, D.: Closure properties in the class of multiple context- free groups. Groups Complex. Cryptol.11(1), 1–15 (2019).https://doi.org/10. 1515/gcc-2019-2004

2019
[26]

In: Twenty years of theoretical and practical synergies, Lecture Notes in Comput

Lohrey, M.: Membership problems in infinite groups. In: Twenty years of theoretical and practical synergies, Lecture Notes in Comput. Sci., vol. 14773, pp. 44–59. Springer, Cham ([2024]©2024).https://doi.org/10.1007/ 978-3-031-64309-5_5

2024
[27]

In: Groups St Andrews 2013, London Math

Lohrey, M.: The rational subset membership problem for groups: a survey. In: Groups St Andrews 2013, London Math. Soc. Lecture Note Ser., vol. 422, pp. 368–389. Cambridge Univ. Press, Cambridge (2015)

2013
[28]

Makanin, G.S.: Equations in a free group. Izv. Akad. Nauk SSSR Ser. Mat.46(6), 1199–1273, 1344 (1982) Visibly Pushdown Languages in Groups 17

1982
[29]

In: Automata, languages and programming (Proc

Mehlhorn, K.: Pebbling mountain ranges and its application to DCFL recognition. In: Automata, languages and programming (Proc. Seventh Internat. Colloq., No- ordwijkerhout,1980),LectureNotesinComput.Sci.,vol.85,pp.422–435.Springer, Berlin-New York (1980)

1980
[30]

Muller, D.E., Schupp, P.E.: Groups, the theory of ends, and context-free lan- guages. J. Comput. System Sci.26(3), 295–310 (1983).https://doi.org/10. 1016/0022-0000(83)90003-X

1983
[31]

In: Descriptional complexity of formal systems, Lecture Notes in Comput

Okhotin, A., Salomaa, K.: The quotient operation on input-driven pushdown au- tomata. In: Descriptional complexity of formal systems, Lecture Notes in Comput. Sci., vol. 10316, pp. 299–310. Springer, Cham (2017).https://doi.org/10.1007/ 978-3-319-60252-3

2017
[32]

Salvati, S.: MIX is a 2-MCFL and the word problem inZ2 is captured by the IO and the OI hierarchies. J. Comput. System Sci.81(7), 1252–1277 (2015).https: //doi.org/10.1016/j.jcss.2015.03.004

work page doi:10.1016/j.jcss.2015.03.004 2015