
The Library
Decision procedures for families of deterministic pushdown automata
Tools
Valiant, Leslie (1973) Decision procedures for families of deterministic pushdown automata. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
The existence and complexity of decision procedures for families of deterministic pushdown automata are investigated, with special emphasis on positive decidability results for those questions, such as equivalence, which are known to become undecidable when the deterministic restriction is removed. The equivalence problem is proved decidable for the following three deterministic families, all of which are already extensive enough to have undecidable inclusion problems: (a) nonsingular automata - a realtime subfamily, which extends the largest corresponding classes with previously known equivalence tests, (b) finite-turn automata - characterised by having a bound on the number of times the direction of the stack movement can change, and (c) one-counter automata - defined by restricting the stack alphabet to just one symbol. The problem of whether a language defined by a machine in one family, can be recognised by one in another, is a convenient formulation of numerous decidable or potentially decidable questions. We show that such questions as whether a deterministic context-free language can be recognised by a machine in any one of the above named classes, must be, if decidable at all, at least as difficult to decide as whether such a language is regular. We re-examine the regularity test of Stearns, and obtain an improved algorithm. We do this by reducing by an exponential order the upper bound on the possible state complexity of regular sets recognised by deterministic pushdown automata of a given size, to a level close to one known to be achievable. We pursue an application of this analysis to a schema theoretic problem. We consider the succinctness with which certain functional schemas can be used to express equivalent large flowchart schemas, and obtain closely matching upper and lower bounds for a measure of this.
Item Type: | Report | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Machine theory | ||||
Series Name: | Theory of Computation Report | ||||
Publisher: | University of Warwick. Department of Computer Science | ||||
Official Date: | August 1973 | ||||
Dates: |
|
||||
Number: | Number 1 | ||||
Number of Pages: | 140 | ||||
DOI: | CS-RR-001 | ||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Computer Science | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Unpublished | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Description: | See Related URL for option to download full text |
||||
Version or Related Resource: | Valiant, L.G. (1973). Decision procedures for families of deterministic pushdown automata. Ph.D. thesis. University of Warwick | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |