On Nondeterminism in Programmed Grammars
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F11%3APU96019" target="_blank" >RIV/00216305:26230/11:PU96019 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On Nondeterminism in Programmed Grammars
Original language description
In the present paper, we discuss programmed grammars. More specifically, we discuss their nondeterministic behaviour and its reduction. We prove that for every programmed grammar, there exists an equivalent programmed grammar where only a single rule hasmore than one successor. Furthermore, we establish an infinite hierarchy of language families resulting from the cardinality of successor sets. Open problem areas are formulated in the conclusion of the paper.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
13th International Conference on Automata and Formal Languages
ISBN
978-615-5097-19-5
ISSN
—
e-ISSN
—
Number of pages
13
Pages from-to
316-328
Publisher name
Computer and Automation Research Institute, Hungarian Academy of Sciences
Place of publication
Debrecen
Event location
Debrecen
Event date
Aug 17, 2011
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—