Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Decision procedures for families of deterministic pushdown automata

Tools
- Tools
+ Tools

Valiant, Leslie (1973) Decision procedures for families of deterministic pushdown automata. PhD thesis, University of Warwick.

[img]
Preview
PDF
WRAP_THESIS_Valiant_1973.pdf - Submitted Version - Requires a PDF viewer.

Download (5Mb)
Official URL: http://webcat.warwick.ac.uk/record=b1746283~S15

Request Changes to record.

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: Thesis or Dissertation (PhD)
Subjects: Q Science > QA Mathematics
Library of Congress Subject Headings (LCSH): Machine theory
Official Date: July 1973
Dates:
DateEvent
July 1973Submitted
Institution: University of Warwick
Theses Department: Department of Computer Science
Thesis Type: PhD
Publication Status: Unpublished
Supervisor(s)/Advisor: Paterson, Michael S.
Sponsors: Science Research Council (Great Britain) (SRC)
Extent: 138 leaves
Language: eng
Related URLs:
  • Related item in WRAP

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us