Source-linked AI summary
Recognizers for Graph-Encoding Languages
Anssi Yli-Jyrä
TL;DR
RIAs address how to decompose two-stack visibly pushdown computations for graph encodings into local finite-state work and persistent recurrent interfaces. The paper defines units that compute interface transformations and layers that compose them, establishing closure properties while showing that emptiness remains undecidable.
Problem
Two-stack visibly pushdown graph-encoding computations combine local computation with stack memory, motivating a decomposition that isolates vertex-local transformations and their recurrent interfaces.
Source: §1 · p. 1Method
RIAs use finite-state units to compute local interface transformations and recurrent layers to compose them, externalizing long-range stack memory into interfaces.
Source: §1 · pp. 1–2Results
Nondeterministic RILs are closed under union, intersection, concatenation, Kleene-∗, and reversal, while deterministic RILs are closed under Boolean operations and RIL emptiness is undecidable.
Source: §1 · p. 2, §5.1 · p. 8, §7 · p. 13Takeaways & Limitations
RIAs provide an algebraic representation that separates local computation from long-range stack memory and supports analysis and composition of interface transformations.
Source: §1 · p. 1, §7 · p. 13Restrictions on interface transformations that recover determinizability and decidability of emptiness remain an open research direction.
Source: §7 · p. 13
Abstract
from arXiv · showhide
We introduce recurrent incidence automata (RIAs), a new automaton model motivated by a decomposition of certain two-stack visibly pushdown computations. The decomposition separates vertex-local finite-state computations from recurrent one-stack interfaces connecting consecutive vertices. The construction is motivated by a two-stack visibly pushdown encoding of arbitrary ordered graphs whose strings admit a unique factorization into center-foldable vertex-local factors and whose auxiliary stack is empty at every factor boundary. Folding each factor into a sequence of pair symbols yields a local interface transformation. An RIA consists of a finite-state unit that computes these transformations and a recurrent layer that composes them across consecutive factors. Rather than manipulating an internal pushdown store, RIAs externalize long-range stack memory into recurrent interfaces between local computations. We show that nondeterministic RIA languages are closed under union, intersection, concatenation, Kleene-*, and reversal. Deterministic RIAs are closed under Boolean operations, although emptiness remains undecidable.
1 Introduction
The paper decomposes a two-stack graph-encoding computation into vertex-local finite-state transformations connected by recurrent one-stack interfaces. This motivates RIAs, which externalize long-range stack memory and support analysis of the interface transformations independently of local computation.
1 Introduction
- RIAs separate local finite-state computation from long-range stack memory by externalizing the latter into recurrent one-stack interfaces.The decomposition is motivated by graph-encoding computations whose auxiliary stack is empty at factor boundaries.Source: §1 · pp. 1–2
- The explicit interface representation is proposed as a basis for graph enumeration, neural-network probing, constrained structure decoding, and related symbolic algorithms.The authors describe it as a reusable algebraic representation of stack behavior that can be analyzed, composed, and constrained independently of local computation.Source: §1 · p. 1
- The underlying encoding uses two independent visibly pushdown structures, with the auxiliary stack accessing the first stack only within vertex-local domains.Its factors represent vertices and their incidences; edges are partitioned into standalone and leaning edges using the proper rope cover.Source: §1 · pp. 1–2
- Center folding compiles each vertex-local two-stack computation into a finite-state transformation that updates the persistent interface.Associative composition of these transformations combines local computations into a global computation.Source: §1 · p. 2
- RIAs introduce visible replace operations that rewrite interface symbols directly, alongside call and return operations.This allows local computations to update graph incidences before their transformations are recurrently composed.Source: §1 · p. 2
- RIAs retain algebraic closure properties, including closure of deterministic RIAs under Boolean operations, while their emptiness problem is undecidable.The paper also defines a subclass recognizing canonical graph encodings.Source: §1 · p. 2
2 Graph-Encoding Strings
Graph-encoding strings combine a unique sequence of vertex-local center-foldable factors with a global balanced-bracket structure. Folding each factor yields pair symbols that describe local changes to a one-stack interface representing active standalone edges.
2 Graph-Encoding Strings
- The partitioned alphabet distinguishes standalone brackets, leaning brackets, and local symbols, with the distinguished local brackets excluded from global matching.Two visibly pushdown languages describe the local factor structure and global bracket balance; their intersection defines the input language recognized by a synchronous two-stack visibly pushdown automaton.Source: §2 · p. 3
- Each ordered graph is encoded as a double-balanced word, with one center-foldable factor per vertex in vertex order.The input combines unique local factorization with global balance of the standalone and leaning brackets after local symbols are erased.Source: §2 · p. 3
- Hierarchical bracketing represents standalone edges as complete bracket chains and leaning edges through chains that share an endpoint with a standalone edge.When a leaning edge has two supporting standalone edges, the encoding avoids redundant representations by using only the shared endpoint.Source: §2 · p. 4
- The proper rope cover determines the partition into standalone and leaning edges, and minimizes the number of standalone edges.Although leaning edges may be unbounded in number, information flow between a standalone edge’s shared endpoint and its leaning edges remains bounded.Source: §2 · p. 4
- Center folding replaces symmetric symbol pairs in a factor with pair symbols, producing the sequence used to describe that vertex’s interface transformation.The encoding uses specified pair classes from the full pair alphabet.Source: §2 · p. 4
- The active standalone edges form the one-stack interface between factors, while each folded factor describes vertex-local changes to it.A vertex can open or close a standalone edge, access an active edge through a leaning bracket, or leave the interface unchanged.Source: §2 · p. 4
3 Recurrent Incidence Automata
An RIA unit reads the folded symbols of one factor and transforms an input interface into an output interface; an RIA layer recurrently composes those transformations across factors. The model extends visibly pushdown operations with visible replacement of interface symbols.
3 Recurrent Incidence Automata
- RIAs use visible call, return, and replace operations to update an interface, then recurrently compose local transformations along vertex-local factors.Replace operations rewrite interface symbols directly, avoiding explicit unwrapping and rewrapping of the intervening stack prefix.Source: §3 · p. 5
- An RIA unit is a finite-state machine that reads folded symbol pairs and transforms an input interface into an output interface.Each transition consumes and emits an interface symbol or ε at the currently accessed position; the residual suffix remains unchanged.Source: §3 · pp. 5–6
- The transition classes encode calls that insert symbols, returns that remove them, replacements that rewrite accessed symbols, and internal transitions.Initial transitions also propagate the recurrent layer’s finite-state control between interfaces.Source: §3 · pp. 5–6
- An RIA layer recognizes strings by recurrently composing its unit’s stack-transformation relation and checking initial and final carrier symbols.Languages recognized by RIA layers are called RILs; the maximal layer accepts all RIA-admissible strings.Source: §3 · pp. 6–7
4 Normalisations
The normalizations show that RILs can be represented with constrained carrier symbols and complete units. These transformations preserve the recognized language, and completion can preserve determinism.
4 Normalisations
- Any RIL has an equivalent layer whose initial and final carriers never occur in stacks containing other elements.The construction uses distinguished carrier copies for singleton stacks and ordinary copies for occurrences below other symbols.Source: §4 · p. 7
- Every RIL has an equivalent complete RIA layer, and the complete layer can remain deterministic when the original layer is deterministic.A fresh rejecting stack symbol ensures computations entering the completion component cannot accept.Source: §4 · p. 7
- A unit is functional when its stack-transformation relation is a partial function, and unambiguous when each relation tuple has a unique accepting computation.A layer is deterministic when its carrier set is a singleton and its unit is functional; the underlying unit may still be nondeterministic.Source: §4 · p. 7
5 Closure Properties
The section establishes closure properties for general recurrent incidence languages before treating graph-encoding languages as a distinguished subclass.
5.1 Unrestricted RILs
- Unrestricted RILs are closed under union, intersection, concatenation, Kleene-∗, and reversal; they intersect compatible VPLs and are contained in 2MVPL.The intersection preserves determinism when the RIL is deterministic.Source: §5.1 · pp. 8–9
5.2 Deterministic RILs
- DRILs are closed under all Boolean operations, with complement defined relative to the maximal layer.Source: §5.2 · p. 9
5.3 Unit-Acyclic RILs
- Unit-acyclic RILs are VPLs, are deterministic RILs, and are closed under relative complement.Acyclicity leaves only finitely many local interface transformations, which can be stored in VPA control.Source: §5.3 · p. 10
5.4 Graph-Encoding RILs
- The deterministic automaton S recognizes exactly canonical ordered-graph encodings; GRILs are closed under union, intersection, concatenation, and Kleene-∗, while deterministic GRILs are closed under complement.Concatenation and Kleene-∗ juxtapose complete code strings, representing disjoint graphs without joining them.Source: §5.4 · p. 11
6 Decision Problems and Family Inclusions
The section places RIL strictly inside CSL while showing that RIL is not contained in CFL. It also distinguishes decidability for UARIL from undecidability for DRIL and RIL.
Decision problems
- Emptiness, containment, and equivalence are decidable for UARIL but undecidable for DRIL and RIL.The DRIL undecidability proof reduces the halting problem for deterministic two-counter machines to emptiness.Source: §6 · pp. 11–12
Family inclusions
- VPL is not contained in RIL.The proof uses that every RIL is contained in ∇* while a one-symbol language belongs to REG but not RIL.Source: §6 · p. 11
- RIL is a strict subset of CSL, and the section separately establishes that RIL is not contained in CFL.The membership proof places RIL in NSPACE(n)=CSL; a separate theorem gives the non-CFL result.Source: §6 · pp. 11–12
7 Conclusion
The conclusion presents RIAs as a way to separate vertex-local finite-state computation from persistent stack memory carried by recurrent interfaces. It summarizes their language-theoretic properties and identifies restrictions on interface transformations as an open direction.
7 Conclusion
- RIAs decompose certain two-stack visibly pushdown computations into vertex-local interface transformations linked by recurrent one-stack interfaces.They externalize persistent stack memory into the interfaces while confining each local computation to a finite-state unit.Source: §7 · p. 13
- RIL membership is decidable in nondeterministic linear space, deterministic RILs are closed under Boolean operations, and RIL emptiness is undecidable.Unit-acyclic RILs form a subclass of VPLs, while RILs occupy an intermediate position between visibly pushdown and two-stack visibly pushdown languages.Source: §7 · p. 13
- Identifying restrictions on interface transformations that recover determinization and decidability of emptiness remains a research direction.The conclusion also calls for further work on deterministic closure properties and conditions for determinizing RIAs.Source: §7 · p. 13