| |
Okhotin, Alexander |
 |
|
| |
|
Date Reviewed |
|
 |
|
|
|
| |
1 - 4
of 4 reviews |
|
|
|
|
|
|
| |
An extension of context-free grammars with one-sided context specifications
Barash M., Okhotin A. Information and Computation 237268-293, 2014. Type: Article
The gap between context-sensitive languages and context-free languages (types 1 and 2 in the Chomsky hierarchy) has been a rich area of research in formal language theory for the past five decades, giving rise to such mildly context-se...... |
Dec 16 2014 |
|
|
|
|
|
| |
Computational completeness of equations over sets of natural numbers
Jeż A., Okhotin A. Information and Computation 23756-94, 2014. Type: Article
One basic issue in several areas of theoretical computer science is to characterize various classes C of functions or sets as those functions/sets that can be created from certain simple initial objects by means of c...... |
Nov 13 2014 |
|
|
|
|
|
| |
 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 |
|
|
|
|
|
| |
One-visit caterpillar tree automata
Okhotin A., Salomaa K., Domaratzki M. Fundamenta Informaticae 52(4): 361-375, 2002. Type: Article
The standard notion of a tree automaton (whether bottom-up or top-down) is one of parallel operation. A tree-walking automaton is a sequential model where the automaton “walks” on the tree and decides whether to acc...... |
Apr 15 2003 |
|
|
|
|
|
|
|
|
| |
|
|
