| |
Browse All Reviews > Theory Of Computation (F) > Mathematical Logic And Formal Languages (F.4) > Formal Languages (F.4.3) > Classes Defined By Grammars Or Automata (F.4.3...)
|
|
 |
|
|
| |
|
|
| |
1-10 of 34
Reviews about "Classes Defined By Grammars Or Automata (F.4.3...)":
|
Date Reviewed |
| |
Non-recursive trade-offs between two-dimensional automata and grammars
Průša D. Theoretical Computer Science 610, Part A, 121-132, 2016. Type: Article
All computer scientists should be familiar with the theory of one-dimensional strings including the automata that can recognize them and the grammars that generate them. But the two-dimensional version is terra incognita to many, and w...
|
May 20 2016 |
| |
Simple restriction in context-free rewriting
Masopust T. Journal of Computer and System Sciences 76(8): 837-846, 2010. Type: Article
Context-free grammars have long been a useful tool in computer science, and those in the formal language theory field have been studying the expressive power of these systems for a long time. This paper studies the computational comple...
|
Feb 15 2011 |
| |
A second course in formal languages and automata theory
Shallit J., Cambridge University Press, New York, NY, 2008. 260 pp. Type: Book (9780521865722), Reviews: (2 of 2)
In the preface, the author quotes a professor who said that in its attempt to target undergraduate students, the second edition of Hopcroft and Ullman’s classic [1] “removed all the good parts.” Another co...
|
Apr 9 2009 |
| |
A second course in formal languages and automata theory
Shallit J., Cambridge University Press, New York, NY, 2008. 260 pp. Type: Book (9780521865722), Reviews: (1 of 2)
Bucking the trend to “dumb down” content, to make textbooks more broadly accessible for a first-level course, this book is a very welcome effort to woo interested students back to the joys and challenges of more mat...
|
Jan 6 2009 |
| |
Bond-free DNA language classes
Domaratzki M. Natural Computing: an international journal 6(4): 371-402, 2007. Type: Article
A number of properties of classes of bond-free languages are considered in this paper. A close connection to T-codes, a concept that generalizes several classically defined code families, ...
|
Mar 24 2008 |
| |
Linearity and nondeletion on monadic context-free tree grammars
Fujiyoshi A. Information Processing Letters 93(3): 103-107, 2005. Type: Article
This short paper contains two results about context-free tree grammars (CFTGs). Such grammars can be monadic, linear, and/or nondeleting. The linear and nondeleting classifications are associated with like-named restrictions on the tre...
|
Jul 21 2005 |
| |
 Boolean grammars
Okhotin A. Information and Computation 194(1): 19-48, 2004. Type: Article
Context-free grammars possess many desirable properties needed in syntactical descriptions, but their generative capacity is inadequate for describing many languages that arise in practice. Many generalizations of context-free grammars...
|
Jan 12 2005 |
| |
On two-way FA with monotonic counters and quadratic Diophantine equations
Ibarra O., Dang Z. Theoretical Computer Science 312(2-3): 359-378, 2004. Type: Article
Connections between Diophantine equations and a novel kind of two-way counter automaton behavior are explored in this paper. Both deterministic and nondeterministic automata are considered. The counters are monotone; specifically, they...
|
Jun 1 2004 |
| |
On omega context free languages which are Borel sets of infinite rank
Finkel O. Theoretical Computer Science 299(1-3): 327-346, 2003. Type: Article
An investigation into the descriptive set theory aspect of &ohgr;-language theory is continued in this paper. This entire theory has its origins in the pioneering work of Búchi. Landweber essentially settled the classifica...
|
Jan 13 2004 |
| |
Closure and decidability properties of some language classes with respect to ciliate bio-operations
Daley M., Ibarra O., Kari L. Theoretical Computer Science 306(1-3): 19-38, 2003. Type: Article
The paper is an important contribution to certain aspects of DNA computing, dealing with behavioral models for ciliates. The latter are primitive, single-celled organisms that have generated a great deal of interest due to their unique...
|
Dec 17 2003 |
| |
|
|
| |
|
|
