5 papers · 1 filter
Bounded treewidth, multiple context-free grammars, and downward closures
C. Aiswarya, Pascal Baumann, Prakash Saivasan +2
The reachability problem in multi-pushdown automata (MPDA) has many applications in static analysis of recursive programs. An example is safety verification of multi-threaded recur…
Edit Distance of Finite State Transducers
C. Aiswarya, Amaldev Manuel, Saina Sunny
We lift metrics over words to metrics over word-to-word transductions, by defining the distance between two transductions as the supremum of the distances of their respective outpu…
Satisfiability of Context-free String Constraints with Subword-ordering and Transducers
C Aiswarya, Soumodev Mal, Prakash Saivasan
We study the satisfiability of string constraints where context-free membership constraints may be imposed on variables. Additionally a variable may be constrained to be a subword…
Deciding Conjugacy of a Rational Relation
C. Aiswarya, Amaldev Manuel, Saina Sunny
The study of rational relations is fundamental to the study of formal languages and automata theory. A rational relation is conjugate if each pair of words in the relation is conju…
Weighted Tiling Systems for Graphs: Evaluation Complexity
C. Aiswarya, Paul Gastin
We consider weighted tiling systems to represent functions from graphs to a commutative semiring such as the Natural semiring or the Tropical semiring. The system labels the nodes…