Regularity Problems for Visibly Pushdown Languages | Zendy

Vince Bárány | Zendy; Christof Löding | Zendy; Olivier Serre | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Regularity Problems for Visibly Pushdown Languages

Author(s) -

Vince Bárány,

Christof Löding,

Olivier Serre

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-32301-5

DOI - 10.1007/11672142_34

Subject(s) - pushdown automaton , deterministic pushdown automaton , embedded pushdown automaton , computer science , decidability , automaton , nested word , alphabet , context free language , büchi automaton , two way deterministic finite automaton , deterministic automaton , discrete mathematics , theoretical computer science , programming language , mathematics , automata theory , nondeterministic finite automaton , rule based machine translation , artificial intelligence , quantum finite automata , linguistics , context free grammar , parsing , philosophy , tree adjoining grammar

Visibly pushdown automata are special pushdown automata whose stack behavior is driven by the input symbols according to a partition of the alphabet. We show that it is decidable for a given visibly pushdown automaton whether it is equivalent to a visibly counter automaton, i.e. an automaton that uses its stack only as counter. In particular, this allows to decide whether a given visibly pushdown language is a regular restriction of the set of well-matched words, meaning that the language can be accepted by a finite automaton if only well-matched words are considered as input.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research