Normal forms for phrase-structure grammars
RAIRO-Theor. Inf. Appl., 25 5 (1991) 473-496
Published online: 2017-02-01
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
On the computational completeness of generalized forbidding matrix grammars
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi RamanTheoretical Computer Science 999 114539 (2024)
https://doi.org/10.1016/j.tcs.2024.114539
On the computational completeness of several descriptional complexity restrictions of semi-conditional grammars
Henning Fernau, Lakshmanan Kuppusamy and Rufus O. OladeleComputability 1 (2024)
https://doi.org/10.3233/COM-220427
14773 192 (2024)
https://doi.org/10.1007/978-3-031-64309-5_16
Networks of Watson-Crick D0L systems with communication by substrings
Erzsébet Csuhaj-Varjú and György VaszilTheoretical Computer Science 995 114493 (2024)
https://doi.org/10.1016/j.tcs.2024.114493
When Stars Control a Grammar's Work
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi RamanElectronic Proceedings in Theoretical Computer Science 386 96 (2023)
https://doi.org/10.4204/EPTCS.386.9
Improved descriptional complexity results on generalized forbidding grammars
Henning Fernau, Lakshmanan Kuppusamy, Rufus O. Oladele and Indhumathi RamanDiscrete Applied Mathematics 319 2 (2022)
https://doi.org/10.1016/j.dam.2020.12.027
On the computational completeness of matrix simple semi-conditional grammars
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi RamanInformation and Computation 284 104688 (2022)
https://doi.org/10.1016/j.ic.2021.104688
Machines, Computations, and Universality
Lucie Ciencialová, Luděk Cienciala and Erzsébet Csuhaj-VarjúLecture Notes in Computer Science, Machines, Computations, and Universality 13419 75 (2022)
https://doi.org/10.1007/978-3-031-13502-6_5
Conclusive Tree-Controlled Grammars
Dominika Klobučníková, Zbyněk Křivka and Alexander MedunaElectronic Proceedings in Theoretical Computer Science 367 112 (2022)
https://doi.org/10.4204/EPTCS.367.8
$$\mathcal {L}$$-reduction computation revisited
Kaoru Fujioka, Fumiya Okubo and Takashi YokomoriActa Informatica 59 (4) 409 (2022)
https://doi.org/10.1007/s00236-022-00418-0
Membrane Computing
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi RamanLecture Notes in Computer Science, Membrane Computing 12687 31 (2021)
https://doi.org/10.1007/978-3-030-77102-7_3
Developments in Language Theory
Henning FernauLecture Notes in Computer Science, Developments in Language Theory 12811 12 (2021)
https://doi.org/10.1007/978-3-030-81508-0_2
On the computing powers of L-reductions of insertion languages
Fumiya Okubo and Takashi YokomoriTheoretical Computer Science 862 224 (2021)
https://doi.org/10.1016/j.tcs.2020.11.029
Descriptional Complexity of Formal Systems
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi RamanLecture Notes in Computer Science, Descriptional Complexity of Formal Systems 12442 52 (2020)
https://doi.org/10.1007/978-3-030-62536-8_5
Deterministic Lindenmayer Systems with Dynamic Control of Parallelism
Henning Bordihn and György VaszilInternational Journal of Foundations of Computer Science 31 (01) 37 (2020)
https://doi.org/10.1142/S0129054120400031
Universal insertion grammars of size two
Sergey Verlan, Henning Fernau and Lakshmanan KuppusamyTheoretical Computer Science 843 153 (2020)
https://doi.org/10.1016/j.tcs.2020.09.002
On path-controlled insertion–deletion systems
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi RamanActa Informatica 56 (1) 35 (2019)
https://doi.org/10.1007/s00236-018-0312-2
Computational completeness of simple semi-conditional insertion–deletion systems of degree (2,1)
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi RamanNatural Computing 18 (3) 563 (2019)
https://doi.org/10.1007/s11047-019-09742-w
Descriptional Complexity of Formal Systems
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi RamanLecture Notes in Computer Science, Descriptional Complexity of Formal Systems 11612 111 (2019)
https://doi.org/10.1007/978-3-030-23247-4_8
11394 174 (2019)
https://doi.org/10.1007/978-3-030-11509-8_15
Investigations on the power of matrix insertion-deletion systems with small sizes
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi RamanNatural Computing 17 (2) 249 (2018)
https://doi.org/10.1007/s11047-017-9656-8
Sailing Routes in the World of Computation
Henning Fernau, Lakshmanan Kuppusamy and Rufus O. OladeleLecture Notes in Computer Science, Sailing Routes in the World of Computation 10936 172 (2018)
https://doi.org/10.1007/978-3-319-94418-0_18
Modern Language Models and Computation
Alexander Meduna and Ondřej SoukupModern Language Models and Computation 513 (2017)
https://doi.org/10.1007/978-3-319-63100-4_16
On the computational completeness of graph-controlled insertion–deletion systems with binary sizes
Henning Fernau, Lakshmanan Kuppusamy and Indhumathi RamanTheoretical Computer Science 682 100 (2017)
https://doi.org/10.1016/j.tcs.2017.01.019
10329 89 (2017)
https://doi.org/10.1007/978-3-319-60134-2_8
Modern Language Models and Computation
Alexander Meduna and Ondřej SoukupModern Language Models and Computation 57 (2017)
https://doi.org/10.1007/978-3-319-63100-4_3
Unconventional Computation and Natural Computation
Henning Fernau, Lakshmanan Kuppusamy and Sergey VerlanLecture Notes in Computer Science, Unconventional Computation and Natural Computation 10240 182 (2017)
https://doi.org/10.1007/978-3-319-58187-3_14
Phrase-Structure Grammars: Normal Forms and Reduction
Zbyněk Křivka, Alexander Meduna and Petr ZemekThe Computer Journal 59 (8) 1180 (2016)
https://doi.org/10.1093/comjnl/bxw001
Regulated Grammars and Automata
Alexander Meduna and Petr ZemekRegulated Grammars and Automata 191 (2014)
https://doi.org/10.1007/978-1-4939-0369-6_6
Regulated Grammars and Automata
Alexander Meduna and Petr ZemekRegulated Grammars and Automata 653 (2014)
https://doi.org/10.1007/978-1-4939-0369-6_21
Regulated Grammars and Automata
Alexander Meduna and Petr ZemekRegulated Grammars and Automata 39 (2014)
https://doi.org/10.1007/978-1-4939-0369-6_4
One-sided random context grammars with a limited number of right random context rules
Alexander Meduna and Petr ZemekTheoretical Computer Science 516 127 (2014)
https://doi.org/10.1016/j.tcs.2013.11.009
Networks of evolutionary processors: computationally complete normal forms
Jürgen Dassow, Florin Manea and Bianca TrutheNatural Computing 11 (4) 595 (2012)
https://doi.org/10.1007/s11047-012-9331-z
Nonterminal complexity of one-sided random context grammars
Alexander Meduna and Petr ZemekActa Informatica 49 (2) 55 (2012)
https://doi.org/10.1007/s00236-012-0150-6
Handbook of Natural Computing
Masami Hagiya, Satoshi Kobayashi, Ken Komiya, Fumiaki Tanaka and Takashi YokomoriHandbook of Natural Computing 1129 (2012)
https://doi.org/10.1007/978-3-540-92910-9_34
Unconventional Computation
Jürgen Dassow, Florin Manea and Bianca TrutheLecture Notes in Computer Science, Unconventional Computation 6714 89 (2011)
https://doi.org/10.1007/978-3-642-21341-0_14
On the Generative Power of Cancel Minimal Linear Grammars with Single Nonterminal Symbol except the Start Symbol
Kaoru FUJIOKA and Hirofumi KATSUNOIEICE Transactions on Information and Systems E94-D (10) 1945 (2011)
https://doi.org/10.1587/transinf.E94.D.1945
A note on the descriptional complexity of semi-conditional grammars
Fumiya OkuboInformation Processing Letters 110 (1) 36 (2009)
https://doi.org/10.1016/j.ipl.2009.10.002
CD GRAMMAR SYSTEMS WITH REGULAR START CONDITIONS
RUDOLF FREUND and MARION OSWALDInternational Journal of Foundations of Computer Science 19 (04) 767 (2008)
https://doi.org/10.1142/S0129054108005942
Descriptional complexity of multi-parallel grammars
Tomáš MasopustInformation Processing Letters 108 (2) 68 (2008)
https://doi.org/10.1016/j.ipl.2008.04.002
Iterated sequential transducers as language generating devices
Henning Bordihn, Henning Fernau, Markus Holzer, Vincenzo Manca and Carlos Martín-VideTheoretical Computer Science 369 (1-3) 67 (2006)
https://doi.org/10.1016/j.tcs.2006.07.059
Hybrid networks of evolutionary processors are computationally complete
Erzs�bet Csuhaj-Varj�, Carlos Mart�n-Vide and Victor MitranaActa Informatica 41 (4-5) 257 (2005)
https://doi.org/10.1007/s00236-004-0158-7
Formal Languages and Applications
Alexandru MateescuStudies in Fuzziness and Soft Computing, Formal Languages and Applications 148 139 (2004)
https://doi.org/10.1007/978-3-540-39886-8_7
Descriptional Complexity Of Generalized Forbidding Grammars
Alexander Meduna and Martin ŠvecInternational Journal of Computer Mathematics 80 (1) 11 (2003)
https://doi.org/10.1080/00207160304666
Grammars and Automata for String Processing
Markus Holzer, Henning Fernau and Henning BordihnTopics in Computer Mathematics, Grammars and Automata for String Processing 20032543 121 (2003)
https://doi.org/10.1201/9780203009642.ch12
Operations and language generating devices suggested by the genome evolution
Jürgen Dassow, Victor Mitrana and Arto SalomaaTheoretical Computer Science 270 (1-2) 701 (2002)
https://doi.org/10.1016/S0304-3975(01)00096-2
Formal properties of PA-matching
Satoshi Kobayashi, Victor Mitrana, Gheorghe Păun and Grzegorz RozenbergTheoretical Computer Science 262 (1-2) 117 (2001)
https://doi.org/10.1016/S0304-3975(00)00185-7
DNA computing based on splicing: universality results
Gheorghe PăunTheoretical Computer Science 231 (2) 275 (2000)
https://doi.org/10.1016/S0304-3975(99)00104-8
On the history of computer science, computer engineering, and computer technology development in Slovakia
J. Dujnic, N. Fristacky, L. Molnar, I. Plander and B. RovanIEEE Annals of the History of Computing 21 (3) 38 (1999)
https://doi.org/10.1109/85.778981
Jewels are Forever
Vincenzo Manca, Carlos Martin-Vide and Gheorghe PäunJewels are Forever 182 (1999)
https://doi.org/10.1007/978-3-642-60207-8_16
New Trends in Formal Languages
Gianina GeorgescuLecture Notes in Computer Science, New Trends in Formal Languages 1218 330 (1997)
https://doi.org/10.1007/3-540-62844-4_24
Handbook of Formal Languages
Alexandru Mateescu and Arto SalomaaHandbook of Formal Languages 175 (1997)
https://doi.org/10.1007/978-3-642-59136-5_4
Context-free evolutionary grammars and the structural language of nucleic acids
Jürgen Dassow, Victor Mitrana and Arto SalomaaBiosystems 43 (3) 169 (1997)
https://doi.org/10.1016/S0303-2647(97)00036-1
Cancellation in context-free languages: enrichment by reduction
M Jantzen and H PetersenTheoretical Computer Science 127 (1) 149 (1994)
https://doi.org/10.1016/0304-3975(94)90104-X