pith. sign in

arxiv: 1810.12731 · v1 · pith:PYT3343Dnew · submitted 2018-10-30 · 💻 cs.FL

Visibly Pushdown Languages and Free Profinite Algebras

classification 💻 cs.FL
keywords languagespushdownvisiblyalgebraicclassesequationssomealgebras
0
0 comments X
read the original abstract

We build a notion of algebraic recognition for visibly pushdown languages by finite algebraic objects. These come with a typical Eilenberg relationship, now between classes of visibly pushdown languages and classes of finite algebras. Building on that algebraic foundation, we further construct a topological object with one purpose being the possibility to derive a notion of equations, through which it is possible to prove that some given visibly pushdown language is not part of a certain class (or to even show decidability of the membership-problem of the class in some cases). In particular, we obtain a special instance of Reiterman's theorem for pseudo-varieties. These findings are then employed on two subclasses of the visibly pushdown languages, for which we derive concrete sets of equations. For some showcase languages, these equations are utilised to prove non-membership to the previously described classes.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages

    cs.FL 2023-02 unverdicted novelty 7.0

    An algorithm classifies visibly pushdown languages as AC^0, ACC^0-hard, or constant-depth equivalent to unions of newly defined intermediate VPLs.