Standard

Contextual grammars with uniform sets of trajectories. / Okhotin, Alexander; Salomaa, Kai.

In: Fundamenta Informaticae, Vol. 64, No. 1-4, 07.09.2005, p. 341-351.

Research output: Contribution to journal › Article › peer-review

Harvard

Okhotin, A & Salomaa, K 2005, 'Contextual grammars with uniform sets of trajectories', Fundamenta Informaticae, vol. 64, no. 1-4, pp. 341-351.

APA

Okhotin, A., & Salomaa, K. (2005). Contextual grammars with uniform sets of trajectories. Fundamenta Informaticae, 64(1-4), 341-351.

Vancouver

Okhotin A, Salomaa K. Contextual grammars with uniform sets of trajectories. Fundamenta Informaticae. 2005 Sep 7;64(1-4):341-351.

Author

Okhotin, Alexander ; Salomaa, Kai. / Contextual grammars with uniform sets of trajectories. In: Fundamenta Informaticae. 2005 ; Vol. 64, No. 1-4. pp. 341-351.

BibTeX

@article{b4de3fc2624f43689d0ad011aab4e605,
title = "Contextual grammars with uniform sets of trajectories",
abstract = "A uniformcontextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the nonuniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.",
keywords = "Context-free language, Contextual grammar, Regular language, Trajectory",
author = "Alexander Okhotin and Kai Salomaa",
year = "2005",
month = sep,
day = "7",
language = "English",
volume = "64",
pages = "341--351",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "1-4",

}

RIS

TY - JOUR

T1 - Contextual grammars with uniform sets of trajectories

AU - Okhotin, Alexander

AU - Salomaa, Kai

PY - 2005/9/7

Y1 - 2005/9/7

N2 - A uniformcontextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the nonuniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.

AB - A uniformcontextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the nonuniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.

KW - Context-free language

KW - Contextual grammar

KW - Regular language

KW - Trajectory

UR - http://www.scopus.com/inward/record.url?scp=24044541405&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:24044541405

VL - 64

SP - 341

EP - 351

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1-4

ER -

ID: 41144246