A graph-based regularity test for deterministic context-free languages (Q1177178): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Q5753522 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4198075 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: A regularity test for pushdown machines / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Regularity and Related Problems for Deterministic Pushdown Automata / rank | |||
Normal rank | |||
Latest revision as of 11:26, 15 May 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A graph-based regularity test for deterministic context-free languages |
scientific article |
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
