Superdeterministic PDAs

Publisher Website
Google Scholar
Abstract
A deterministic pushdown store automaton ~s superdetermm~suc if it is finite delay, and whenever two accessible configurations c~ and c~ in the same state and m reading mode are taken by the same input into two configurations c, and c', m reading mode, then c, and c'_, are also m the same state and the change m stack height between c, and c_, is the same as between c~ and c'_, it is decidable whether a deterministic pushdown store automaton is superdetermmistic Let L(M) denote the language accepted by M by final state and empty store A language L is superdetermmlstic if there ,s a superdetermmtstlc pushdown store automaton M such that either L = L(M) or L$ = L(M) for some symbol $, thus, endmarkers are allowed The famdy of superdetermmlstic languages is an AFDL containing all parenthesis languages and all Dyck sets, and it is incomparable with the famdy of nonsingular languages It is decidable whether L(M 0 C L(M.,) for M~ an arbarary nondetermmlstlc pushdown store automaton and Mz superdetermmlstlc, in time proportional to 2-''"' for p(n) a polynomial in the size of the machines It is hkewlse deodable m time2 z'''' whether L(MJ = L(Mz) for M~ an arbitrary deterministic pushdown store automaton and M, superdetermmlst~c

This publication has 14 references indexed in Scilit: