A polynomial procedure for trimming visibly pushdown automata

We describe a polynomial procedure which, given a visibly pushdown automaton that accepts only well-nested words, returns an equivalent visibly pushdown automaton that is trimmed. We also show that this procedure can be applied to weighted visibly pushdown automata such as visibly pushdown transducers.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00606778
Author Caralp, Mathieu, Reynier, Pierre-Alain, Talbot, Jean-Marc
Maintainer CCSD
Last Updated May 23, 2026, 03:58 (UTC)
Created May 23, 2026, 03:58 (UTC)
Identifier hal-00606778
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF) ; Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS)
creator Caralp, Mathieu
date 2011-07-07T00:00:00
harvest_object_id 158be0ee-e0a0-4870-8d41-0b1728cf9a2a
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2023-11-12T00:00:00
set_spec type:REPORT