A graph-based regularity test for deterministic context-free languages (Q1177178)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 20027
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A graph-based regularity test for deterministic context-free languages |
scientific article; zbMATH DE number 20027 |
Statements
A graph-based regularity test for deterministic context-free languages (English)
0 references
26 June 1992
0 references
It is shown that there exists a test of complexity \(O((qt)^ 2 t^{qt})\) for testing the regularity of a deterministic context-free language, where \(q\) is the number of states and \(t\) is the stack alphabet size of the pushdown automaton derived from an \(LR(1)\) grammar for the languages. The previously established upper bound for the test was \(t^{q^ q}\).
0 references
context-free languages
0 references
pushdown automata
0 references
0.7910188436508179
0 references
0.7864599227905273
0 references
0.781216025352478
0 references
