text:
Talk:Computer-generated art

Overlapping articles
The following articles overlap:

 * Computer art
 * Computer-generated art
 * Digital art

I realize that "digital art" and "computer art" have technically different meanings, but in practice they almost always refer to the same thing, and they're resulting in similar articles. Wikipedia is not a dictionary. They need to be merged into one article, either digital art or computer art or similar.Computer-generated art can be confusing.

Note the existence of these more specific articles:

 * Generative art
 * Computer graphics
 * Digital painting
 * 3D computer graphics
 * 2D computer graphics

FAL 08:40, 27 July 2006 (UTC)

Untitled
While I can't say that I'm feeling up to a re-write at the moment (later perhaps...) I think this article isn't quite on the spot. The scholarly artistic discussion I've been involved in recently has a clear delineation between "computer-generated" art and "digital" (for the sake of comparison, "computer-assisted") art. "Computer-generated" implies that a computer actually generated the image. "But how could a computer (a machine with no apparent self-awareness) create a work of art?" Simple. A human writes a piece of code and feeds a seed value into the machine, which then outputs a graphic file or printed image. In a way, this is fractal art (though not necessarily the colorful psychedelia many of you may be thinking of) and may not at all be aesthetically pleasing to the majority of human beings. However, there are some examples of computer-generated art (I'm missing my reference at the moment...) which use genetic algorithms, their output evolving over time which have produced quite pleasing images.

Now, the digital ("computer-assisted") art I referred to above could be any number of still or motion images (in 2 or 3 dimensions), audio signals (of any timbre or duration), and/or combinations thereof -- maybe or maybe not of the interactive persuasion. Accessible software (such as Adobe Photoshop and Macromedia Director) as well as hardware (such as the Canon GL1, Epson Stylus-series printers, and the computer that basically runs all of the above) have made it possible for (m)anyone to enhance, improve, accelerate, or even BEGIN her artistics process. This is not to imply that taking a few snapshots with your neighbor's digital camera and inverting the colors makes someone an artist... However, these digital tools have made it easier and faster for many artistic projects to take flight. Or take flight faster. (I might also add, that programs like Photoshop have done wonders for the world of montage lately...) So anyway, those are a few things to think about. BUT... As a quick closer, suppose Cristo uses a computer for his wrapping projects, would they then be digital art?

I've started a rewrite. I deleted a bunch of irrelevant stuff; it's in the history.

TODO, from the old article:

 * Discuss painting.
 * Image manipulation.
 * Compositing.
 * Animation.
 * Output.
 * But is it art?
 * The future.

-- Merphant

Aaron by Harold Cohen
Is definately worth a mention as an example of computer-generated art. See for example:

http://www.aaai.org/AITopics/html/art.html

=
============================================================

how is it art if the computer makes it for you. all you do is push a few buttons and the cpu does all the work.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Talk:Computer-generated art


text:
Context-free grammar

In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context. In particular, in a context-free grammar, each production rule is of the form

 * $$A\ \to\ \alpha$$

with $$A$$ a single nonterminal symbol, and $$\alpha$$ a string of terminals and/or nonterminals ($$\alpha$$ can be empty). Regardless of which symbols surround it, the single nonterminal $$A$$ on the left hand side can always be replaced by $$\alpha$$ on the right hand side. This distinguishes it from a context-sensitive grammar, which can have production rules in the form $$\alpha A \beta \rightarrow \alpha \gamma \beta$$ with $$A$$ a nonterminal symbol and $$\alpha$$, $$\beta$$, and $$\gamma$$ strings of terminal and/or nonterminal symbols.

A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the first rule in the picture,

 * $$\langle\text{Stmt}\rangle \to \langle\text{Id}\rangle = \langle\text{Expr}\rangle ;$$

replaces $$\langle\text{Stmt}\rangle$$ with $$\langle\text{Id}\rangle = \langle\text{Expr}\rangle ;$$. There can be multiple replacement rules for a given nonterminal symbol. The language generated by a grammar is the set of all strings of terminal symbols that can be derived, by repeated rule applications, from some particular nonterminal symbol ("start symbol"). Nonterminal symbols are used during the derivation process, but do not appear in its final result string.

Languages generated by context-free grammars are known as context-free languages (CFL). Different context-free grammars can generate the same context-free language. It is important to distinguish the properties of the language (intrinsic properties) from the properties of a particular grammar (extrinsic properties). The language equality question (do two given context-free grammars generate the same language?) is undecidable.

Context-free grammars arise in linguistics where they are used to describe the structure of sentences and words in a natural language, and they were invented by the linguist Noam Chomsky for this purpose. By contrast, in computer science, as the use of recursively-defined concepts increased, they were used more and more. In an early application, grammars are used to describe the structure of programming languages. In a newer application, they are used in an essential part of the Extensible Markup Language (XML) called the document type definition.

In linguistics, some authors use the term phrase structure grammar to refer to context-free grammars, whereby phrase-structure grammars are distinct from dependency grammars. In computer science, a popular notation for context-free grammars is Backus–Naur form, or BNF.

Background
Since at least the time of the ancient Indian scholar Pāṇini, linguists have described the grammars of languages in terms of their block structure, and described how sentences are recursively built up from smaller phrases, and eventually individual words or word elements. An essential property of these block structures is that logical units never overlap. For example, the sentence:
 * John, whose blue car was in the garage, walked to the grocery store.

can be logically parenthesized (with the logical metasymbols [ ]) as follows:
 * [John[, [whose [blue car]] [was [in [the garage]]],]] [walked [to [the [grocery store]]]].

A context-free grammar provides a simple and mathematically precise mechanism for describing the methods by which phrases in some natural language are built from smaller blocks, capturing the "block structure" of sentences in a natural way. Its simplicity makes the formalism amenable to rigorous mathematical study. Important features of natural language syntax such as agreement and reference are not part of the context-free grammar, but the basic recursive structure of sentences, the way in which clauses nest inside other clauses, and the way in which lists of adjectives and adverbs are swallowed by nouns and verbs, is described exactly.

Context-free grammars are a special form of Semi-Thue systems that in their general form date back to the work of Axel Thue.

The formalism of context-free grammars was developed in the mid-1950s by Noam Chomsky, and also their classification as a special type of formal grammar (which he called phrase-structure grammars). Some authors, however, reserve the term for more restricted grammars in the Chomsky hierarchy: context-sensitive grammars or context-free grammars. In a broader sense, phrase structure grammars are also known as constituency grammars. The defining trait of phrase structure grammars is thus their adherence to the constituency relation, as opposed to the dependency relation of dependency grammars. In Chomsky's generative grammar framework, the syntax of natural language was described by context-free rules combined with transformation rules.

Block structure was introduced into computer programming languages by the Algol project (1957–1960), which, as a consequence, also featured a context-free grammar to describe the resulting Algol syntax. This became a standard feature of computer languages, and the notation for grammars used in concrete descriptions of computer languages came to be known as Backus–Naur form, after two members of the Algol language design committee. The "block structure" aspect that context-free grammars capture is so fundamental to grammar that the terms syntax and grammar are often identified with context-free grammar rules, especially in computer science. Formal constraints not captured by the grammar are then considered to be part of the "semantics" of the language.

Context-free grammars are simple enough to allow the construction of efficient parsing algorithms that, for a given string, determine whether and how it can be generated from the grammar. An Earley parser is an example of such an algorithm, while the widely used LR and LL parsers are simpler algorithms that deal only with more restrictive subsets of context-free grammars.

Formal definitions
A context-free grammar $G$ is defined by the 4-tuple $$G = (V, \Sigma, R, S)$$, where
 * 1) $V$ is a finite set; each element $$ v\in V$$ is called a nonterminal character or a variable. Each variable represents a different type of phrase or clause in the sentence. Variables are also sometimes called syntactic categories. Each variable defines a sub-language of the language defined by $G$.
 * 2) $Σ$ is a finite set of terminals, disjoint from $V$, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar $G$.
 * 3) $R$ is a finite relation in $$V\times(V\cup\Sigma)^{*}$$, where the asterisk represents the Kleene star operation. The members of $R$ are called the (rewrite) rules or productions of the grammar. (also commonly symbolized by a $P$)
 * 4) $S$ is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of $V$.

Production rule notation
A production rule in $R$ is formalized mathematically as a pair $$(\alpha, \beta)\in R$$, where $$\alpha \in V$$ is a nonterminal and $$\beta \in (V\cup\Sigma)^{*}$$ is a string of variables and/or terminals; rather than using ordered pair notation, production rules are usually written using an arrow operator with $$\alpha$$ as its left hand side and $β$ as its right hand side: $$\alpha\rightarrow\beta$$.

It is allowed for $β$ to be the empty string, and in this case it is customary to denote it by ε. The form $$\alpha\rightarrow\varepsilon$$ is called an $ε$-production.

It is common to list all right-hand sides for the same left-hand side on the same line, using | (the vertical bar) to separate them. Rules $$\alpha\rightarrow \beta_1$$ and $$\alpha\rightarrow\beta_2$$ can hence be written as $$\alpha\rightarrow\beta_1\mid\beta_2$$. In this case, $$\beta_1$$ and $$\beta_2$$ are called the first and second alternative, respectively.

Rule application
For any strings $$u, v\in (V\cup\Sigma)^{*}$$, we say $u$ directly yields $v$, written as $$u\Rightarrow v\,$$, if $$\exists (\alpha, \beta)\in R$$ with $$\alpha \in V$$ and $$u_{1}, u_{2}\in (V\cup\Sigma)^{*}$$ such that $$u\,=u_{1}\alpha u_{2}$$ and $$v\,=u_{1}\beta u_{2}$$. Thus, $v$ is a result of applying the rule $$(\alpha, \beta)$$ to $u$.

Repetitive rule application
For any strings $$u, v\in (V\cup\Sigma)^{*}, $$ we say $u$ yields $v$ or $v$ is derived from $u$ if there is a positive integer $k$ and strings $$u_{1}, \ldots, u_{k}\in (V\cup\Sigma)^{*}$$ such that $$u = u_{1} \Rightarrow u_{2} \Rightarrow \cdots \Rightarrow u_{k} = v$$. This relation is denoted $$u\stackrel{*}{\Rightarrow} v$$, or $$u\Rightarrow\Rightarrow v$$ in some textbooks. If $$k\geq 2$$, the relation $$u\stackrel{+}{\Rightarrow} v$$ holds. In other words, $$(\stackrel{*}{\Rightarrow})$$ and $$(\stackrel{+}{\Rightarrow})$$ are the reflexive transitive closure (allowing a string to yield itself) and the transitive closure (requiring at least one step) of $$(\Rightarrow)$$, respectively.

Context-free language
The language of a grammar $$G = (V, \Sigma, R, S)$$ is the set
 * $$L(G) = \{ w\in\Sigma^{*} : S\stackrel{*}{\Rightarrow} w\}$$

of all terminal-symbol strings derivable from the start symbol.

A language $L$ is said to be a context-free language (CFL), if there exists a CFG $G$, such that $$L\,=\,L(G)$$.

Non-deterministic pushdown automata recognize exactly the context-free languages.

Words concatenated with their reverse
The grammar $$G = (\{S\}, \{a, b\}, P, S)$$, with productions

is context-free. It is not proper since it includes an ε-production. A typical derivation in this grammar is

This makes it clear that $$L(G) = \{ww^R:w\in\{a,b\}^*\}$$. The language is context-free, however, it can be proved that it is not regular.

If the productions

are added, a context-free grammar for the set of all palindromes over the alphabet $S → aSa$ is obtained.

Well-formed parentheses
The canonical example of a context-free grammar is parenthesis matching, which is representative of the general case. There are two terminal symbols "(" and ")" and one nonterminal symbol S. The production rules are

The first rule allows the S symbol to multiply; the second rule allows the S symbol to become enclosed by matching parentheses; and the third rule terminates the recursion.

Well-formed nested parentheses and square brackets
A second canonical example is two different kinds of matching nested parentheses, described by the productions:

with terminal symbols [ ] and nonterminal S.

The following sequence can be derived in that grammar:

Matching pairs
In a context-free grammar, we can pair up characters the way we do with brackets. The simplest example:

This grammar generates the language $$ \{ a^n b^n : n \ge 1 \} $$, which is not regular (according to the pumping lemma for regular languages).

The special character ε stands for the empty string. By changing the above grammar to

we obtain a grammar generating the language $$ \{ a^n b^n : n \ge 0 \} $$ instead. This differs only in that it contains the empty string while the original grammar did not.

Distinct number of a's and b's
A context-free grammar for the language consisting of all strings over {a,b} containing an unequal number of a's and b's:

Here, the nonterminal T can generate all strings with more a's than b's, the nonterminal U generates all strings with more b's than a's and the nonterminal V generates all strings with an equal number of a's and b's. Omitting the third alternative in the rules for T and U does not restrict the grammar's language.

Second block of b's of double size
Another example of a non-regular language is $$ \{ \text{b}^n \text{a}^m \text{b}^{2n} : n \ge 0, m \ge 0 \} $$. It is context-free as it can be generated by the following context-free grammar:

First-order logic formulas
The formation rules for the terms and formulas of formal logic fit the definition of context-free grammar, except that the set of symbols may be infinite and there may be more than one start symbol.

Examples of languages that are not context free
In contrast to well-formed nested parentheses and square brackets in the previous section, there is no context-free grammar for generating all sequences of two different types of parentheses, each separately balanced disregarding the other, where the two types need not nest inside one another, for example:

or

The fact that this language is not context free can be proven using pumping lemma for context-free languages and a proof by contradiction, observing that all words of the form $$ {(}^n {[}^n {)}^n {]}^n $$ should belong to the language. This language belongs instead to a more general class and can be described by a conjunctive grammar, which in turn also includes other non-context-free languages, such as the language of all words of the form $$ \text{a}^n \text{b}^n \text{c}^n $$.

Regular grammars
Every regular grammar is context-free, but not all context-free grammars are regular. The following context-free grammar, for example, is also regular.

The terminals here are $S → bSb$ and $S → ε$, while the only nonterminal is $S → aSa → aaSaa → aabSbaa → aabbaa$. The language described is all nonempty strings of $$a$$s and $$b$$s that end in $$a$$.

This grammar is regular: no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side.

Every regular grammar corresponds directly to a nondeterministic finite automaton, so we know that this is a regular language.

Using vertical bars, the grammar above can be described more tersely as follows:

Derivations and syntax trees
A derivation of a string for a grammar is a sequence of grammar rule applications that transform the start symbol into the string. A derivation proves that the string belongs to the grammar's language.

A derivation is fully determined by giving, for each step: For clarity, the intermediate string is usually given as well.
 * the rule applied in that step
 * the occurrence of its left-hand side to which it is applied

For instance, with the grammar:

the string

can be derived from the start symbol $S → a$ with the following derivation:

 * $S → b$ (by rule 1. on ${ a, b }$)
 * $S → SS$ (by rule 1. on the second $S → (S)$)
 * $S →$ (by rule 2. on the first $S → SS$)
 * $S →$ (by rule 2. on the second $S → (S)$)
 * $S → []$ (by rule 3. on the third $S → [S]$)
 * $([ [ [ [ ][ ] ] ]([ ]) ])$ (by rule 3. on the third $S → aSb$)

Often, a strategy is followed that deterministically chooses the next nonterminal to rewrite:

 * in a leftmost derivation, it is always the leftmost nonterminal;
 * in a rightmost derivation, it is always the rightmost nonterminal.

Given such a strategy, a derivation is completely determined by the sequence of rules applied. For instance, one leftmost derivation of the same string is

 * $S → ab$ (by rule 1 on the leftmost $S → aSb$)
 * $S → ε$ (by rule 2 on the leftmost $''S → T$)
 * $''T → VaT$ (by rule 1 on the leftmost $''U → VbU$)
 * $''V → aVbV$ (by rule 2 on the leftmost $S → bSbb | A$)
 * $A → aA | ε$ (by rule 3 on the leftmost $[ ( ] )$),
 * $[ [ [ [(((( ] ] ] ]))))(([ ))(([ ))([ )( ])( ])( ])$ (by rule 3 on the leftmost $S → a$),

which can be summarized as

 * rule 1
 * rule 2
 * rule 1
 * rule 2
 * rule 3.

One rightmost derivation is:

 * $S → aS$ (by rule 1 on the rightmost $S → bS$)
 * $a$ (by rule 1 on the rightmost $b$)
 * $S$ (by rule 3 on the rightmost $S → a | aS | bS$)
 * $S → S + S$ (by rule 2 on the rightmost $S → 1$)
 * $S → a$ (by rule 2 on the rightmost $1 + 1 + a$),
 * $S$ (by rule 2 on the rightmost $S$),

which can be summarized as

 * rule 1
 * rule 1
 * rule 3
 * rule 2
 * rule 2.

The distinction between leftmost derivation and rightmost derivation is important because in most parsers the transformation of the input is defined by giving a piece of code for every grammar rule that is executed whenever the rule is applied. Therefore, it is important to know whether the parser determines a leftmost or a rightmost derivation because this determines the order in which the pieces of code will be executed. See for an example LL parsers and LR parsers.

A derivation also imposes in some sense a hierarchical structure on the string that is derived. For example, if the string "1 + 1 + a" is derived according to the leftmost derivation outlined above, the structure of the string would be:

where $→ S + S$ indicates a substring recognized as belonging to $S$. This hierarchy can also be seen as a tree:

This tree is called a parse tree or "concrete syntax tree" of the string, by contrast with the abstract syntax tree. In this case the presented leftmost and the rightmost derivations define the same parse tree; however, there is another rightmost derivation of the same string

 * $→ S + S + S$ (by rule 1 on the rightmost $S$)
 * $→ 1 + S + S$ (by rule 3 on the rightmost $S$)
 * $→ 1 + 1 + S$ (by rule 1 on the rightmost $S$)
 * $→ 1 + 1 + a$ (by rule 2 on the rightmost $S$)
 * $S$ (by rule 2 on the rightmost $→ S + S$),
 * $S$ (by rule 2 on the rightmost $→ 1 + S$),

which defines a string with a different structure

and a different parse tree:

Note however that both parse trees can be obtained by both leftmost and rightmost derivations. For example, the last tree can be obtained with the leftmost derivation as follows:

 * $S$ (by rule 1 on the leftmost $→ 1 + S + S$)
 * $S$ (by rule 1 on the leftmost $→ 1 + 1 + S$)
 * $S$ (by rule 2 on the leftmost $→ 1 + 1 + a$)
 * $S$ (by rule 2 on the leftmost $S$)
 * $→ S + S$ (by rule 3 on the leftmost $S$),
 * $→ S + S + S$ (by rule 3 on the leftmost $S$),

If a string in the language of the grammar has more than one parsing tree, then the grammar is said to be an ambiguous grammar. Such grammars are usually hard to parse because the parser cannot always decide which grammar rule it has to apply. Usually, ambiguity is a feature of the grammar, not the language, and an unambiguous grammar can be found that generates the same context-free language. However, there are certain languages that can only be generated by ambiguous grammars; such languages are called inherently ambiguous languages.

Normal forms
Every context-free grammar with no ε-production has an equivalent grammar in Chomsky normal form, and a grammar in Greibach normal form. "Equivalent" here means that the two grammars generate the same language.

The especially simple form of production rules in Chomsky normal form grammars has both theoretical and practical implications. For instance, given a context-free grammar, one can use the Chomsky normal form to construct a polynomial-time algorithm that decides whether a given string is in the language represented by that grammar or not (the CYK algorithm).

Closure properties
Context-free languages are closed under the various operations, that is, if the languages K and L are context-free, so is the result of the following operations:

 * union K ∪ L; concatenation K ∘ L; Kleene star L*
 * substitution (in particular homomorphism)
 * inverse homomorphism
 * intersection with a regular language

They are not closed under general intersection (hence neither under complementation) and set difference.

Decidable problems
The following are some decidable problems about context-free grammars.

Parsing
The parsing problem, checking whether a given word belongs to the language given by a context-free grammar, is decidable, using one of the general-purpose parsing algorithms: Context-free parsing for Chomsky normal form grammars was shown by Leslie G. Valiant to be reducible to Boolean matrix multiplication, thus inheriting its complexity upper bound of O(n2.3728639). Conversely, Lillian Lee has shown O(n3−ε) Boolean matrix multiplication to be reducible to O(n3−3ε) CFG parsing, thus establishing some kind of lower bound for the latter.
 * CYK algorithm (for grammars in Chomsky normal form)
 * Earley parser
 * GLR parser
 * LL parser (only for the proper subclass of for LL(k) grammars)

Reachability, productiveness, nullability
A nonterminal symbol $$X$$ is called productive, or generating, if there is a derivation $$X \stackrel{*}{\Rightarrow} w$$ for some string $$w$$ of terminal symbols. $$X$$ is called reachable if there is a derivation $$S \stackrel{*}{\Rightarrow} \alpha X \beta$$ for some strings $$\alpha,\beta$$ of nonterminal and terminal symbols from the start symbol. $$X$$ is called useless if it is unreachable or unproductive. $$X$$ is called nullable if there is a derivation $$X \stackrel{*}{\Rightarrow} \varepsilon$$. A rule $$X \rightarrow \varepsilon$$ is called an ε-production. A derivation $$X \stackrel{+}{\Rightarrow} X$$ is called a cycle.

Algorithms are known to eliminate from a given grammar, without changing its generated language,
 * unproductive symbols,
 * unreachable symbols,
 * ε-productions, with one possible exception, and
 * cycles.

In particular, an alternative containing a useless nonterminal symbol can be deleted from the right-hand side of a rule. Such rules and alternatives are called useless.

In the depicted example grammar, the nonterminal D is unreachable, and E is unproductive, while C → C causes a cycle. Hence, omitting the last three rules does not change the language generated by the grammar, nor does omitting the alternatives "| Cc | Ee" from the right-hand side of the rule for S.

A context-free grammar is said to be proper if it has neither useless symbols nor ε-productions nor cycles. Combining the above algorithms, every context-free grammar not generating ε can be transformed into a weakly equivalent proper one.

Regularity and LL(k) checks
It is decidable whether a given grammar is a regular grammar, as well as whether it is an LL(k) grammar for a given k≥0. If k is not given, the latter problem is undecidable.

Given a context-free grammar, it is not decidable whether its language is regular, nor whether it is an LL(k) language for a given k.

Emptiness and finiteness
There are algorithms to decide whether the language of a given context-free grammar is empty, as well as whether it is finite.

Undecidable problems
Some questions that are undecidable for wider classes of grammars become decidable for context-free grammars; e.g. the emptiness problem (whether the grammar generates any terminal strings at all), is undecidable for context-sensitive grammars, but decidable for context-free grammars.

However, many problems are undecidable even for context-free grammars; the most prominent ones are handled in the following.

Universality
Given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules?

A reduction can be demonstrated to this problem from the well-known undecidable problem of determining whether a Turing machine accepts a particular input (the halting problem). The reduction uses the concept of a computation history, a string describing an entire computation of a Turing machine. A CFG can be constructed that generates all strings that are not accepting computation histories for a particular Turing machine on a particular input, and thus it will accept all strings only if the machine does not accept that input.

Language equality
Given two CFGs, do they generate the same language?

The undecidability of this problem is a direct consequence of the previous: it is impossible to even decide whether a CFG is equivalent to the trivial CFG defining the language of all strings.

Language inclusion
Given two CFGs, can the first one generate all strings that the second one can generate?

If this problem was decidable, then language equality could be decided too: two CFGs $$G_1$$ and $$G_2$$ generate the same language if $$L(G_1)$$ is a subset of $$L(G_2)$$ and $$L(G_2)$$ is a subset of $$L(G_1)$$.

Being in a lower or higher level of the Chomsky hierarchy
Using Greibach's theorem, it can be shown that the two following problems are undecidable:

 * Given a context-sensitive grammar, does it describe a context-free language?
 * Given a context-free grammar, does it describe a regular language?

Grammar ambiguity
Given a CFG, is it ambiguous?

The undecidability of this problem follows from the fact that if an algorithm to determine ambiguity existed, the Post correspondence problem could be decided, which is known to be undecidable. This may be proved by Ogden's lemma.

Language disjointness
Given two CFGs, is there any string derivable from both grammars?

If this problem was decidable, the undecidable Post correspondence problem (PCP) could be decided, too: given strings $$\alpha_1, \ldots, \alpha_N, \beta_1, \ldots, \beta_N$$ over some alphabet $$\{a_1, \ldots, a_k\}$$, let the grammar $G_1$ consist of the rule
 * $$S \to \alpha_1 S \beta_1^{rev} | \cdots | \alpha_N S \beta_N^{rev} | b$$;

where $$\beta_i^{rev}$$ denotes the reversed string $$\beta_i$$ and $$b$$ does not occur among the $$a_i$$; and let grammar $G_2$ consist of the rule
 * $$T \to a_1 T a_1^{rev} | \cdots | a_k T a_k^{rev} | b$$;

Then the PCP instance given by $$\alpha_1, \ldots, \alpha_N, \beta_1, \ldots, \beta_N$$ has a solution if and only if $L(G_1)$ and $L(G_2)$ share a derivable string. The left of the string (before the $$ b $$) will represent the top of the solution for the PCP instance while the right side will be the bottom in reverse.

Extensions
An obvious way to extend the context-free grammar formalism is to allow nonterminals to have arguments, the values of which are passed along within the rules. This allows natural language features such as agreement and reference, and programming language analogs such as the correct use and definition of identifiers, to be expressed in a natural way. E.g. we can now easily express that in English sentences, the subject and verb must agree in number. In computer science, examples of this approach include affix grammars, attribute grammars, indexed grammars, and Van Wijngaarden two-level grammars. Similar extensions exist in linguistics.

An extended context-free grammar (or regular right part grammar) is one in which the right-hand side of the production rules is allowed to be a regular expression over the grammar's terminals and nonterminals. Extended context-free grammars describe exactly the context-free languages.

Another extension is to allow additional terminal symbols to appear at the left-hand side of rules, constraining their application. This produces the formalism of context-sensitive grammars.

Subclasses
There are a number of important subclasses of the context-free grammars:

 * LR(k) grammars (also known as deterministic context-free grammars) allow parsing (string recognition) with deterministic pushdown automata (PDA), but they can only describe deterministic context-free languages.
 * Simple LR, Look-Ahead LR grammars are subclasses that allow further simplification of parsing. SLR and LALR are recognized using the same PDA as LR, but with simpler tables, in most cases.
 * LL(k) and LL(*) grammars allow parsing by direct construction of a leftmost derivation as described above, and describe even fewer languages.
 * Simple grammars are a subclass of the LL(1) grammars mostly interesting for its theoretical property that language equality of simple grammars is decidable, while language inclusion is not.
 * Bracketed grammars have the property that the terminal symbols are divided into left and right bracket pairs that always match up in rules.
 * Linear grammars have no rules with more than one nonterminal on the right-hand side.
 * Regular grammars are a subclass of the linear grammars and describe the regular languages, i.e. they correspond to finite automata and regular expressions.

LR parsing extends LL parsing to support a larger range of grammars; in turn, generalized LR parsing extends LR parsing to support arbitrary context-free grammars. On LL grammars and LR grammars, it essentially performs LL parsing and LR parsing, respectively, while on nondeterministic grammars, it is as efficient as can be expected. Although GLR parsing was developed in the 1980s, many new language definitions and parser generators continue to be based on LL, LALR or LR parsing up to the present day.

Linguistic applications
Chomsky initially hoped to overcome the limitations of context-free grammars by adding transformation rules.

Such rules are another standard device in traditional linguistics; e.g. passivization in English. Much of generative grammar has been devoted to finding ways of refining the descriptive mechanisms of phrase-structure grammar and transformation rules such that exactly the kinds of things can be expressed that natural language actually allows. Allowing arbitrary transformations does not meet that goal: they are much too powerful, being Turing complete unless significant restrictions are added (e.g. no transformations that introduce and then rewrite symbols in a context-free fashion).

Chomsky's general position regarding the non-context-freeness of natural language has held up since then, although his specific examples regarding the inadequacy of context-free grammars in terms of their weak generative capacity were later disproved. Gerald Gazdar and Geoffrey Pullum have argued that despite a few non-context-free constructions in natural language (such as cross-serial dependencies in Swiss German and reduplication in Bambara ), the vast majority of forms in natural language are indeed context-free.

title: Context-free grammar


text:
Cryonics

Cryonics (from κρύος kryos meaning 'cold') is the low-temperature freezing (usually at −196 C) and storage of human remains, with the speculative hope that resurrection may be possible in the future. Cryonics is regarded with skepticism within the mainstream scientific community. It is generally viewed as a pseudoscience, and its practice has been characterized as quackery.

Cryonics procedures can begin only after the "patients" are clinically and legally dead. Cryonics procedures may begin within minutes of death, and use cryoprotectants to try to prevent ice formation during cryopreservation. It is, however, not possible for a corpse to be reanimated after undergoing vitrification, as this causes damage to the brain including its neural circuits. The first corpse to be frozen was that of James Bedford in 1967. As of 2014, about 250 bodies had been cryopreserved in the United States, and 1,500 people had made arrangements for cryopreservation of their remains.

Economic reality means it is highly improbable that any cryonics corporation could continue in business long enough to take advantage of the claimed long-term benefits offered. Early attempts at cryonic preservation were performed in the 1960s and early 1970s; these ended in failure, with all but one of the companies going out of business, and their stored corpses thawed and disposed of.

Conceptual basis
Cryonicists argue that as long as brain structure remains intact, there is no fundamental barrier, given our current understanding of physical law, to recovering its information content. Cryonics proponents go further than the mainstream consensus in saying that the brain does not have to be continuously active to survive or retain memory. Cryonics controversially states that a human survives even within an inactive brain that has been badly damaged, provided that original encoding of memory and personality can, in theory, be adequately inferred and reconstituted from what structure remains.

Cryonics uses temperatures below −130 °C, called cryopreservation, in an attempt to preserve enough brain information to permit the future revival of the cryopreserved person. Cryopreservation may be accomplished by freezing, freezing with cryoprotectant to reduce ice damage, or by vitrification to avoid ice damage. Even using the best methods, cryopreservation of whole bodies or brains is very damaging and irreversible with current technology.

Cryonics advocates hold that in the future the use of some kind of presently-nonexistent nanotechnology may be able to help bring the dead back to life and treat the diseases which killed them. Mind uploading has also been proposed.

Cryonics in practice
Cryonics can be expensive. , the cost of preparing and storing corpses using cryonics ranged from US$28,000 to $200,000.

When used at high concentrations, cryoprotectants can stop ice formation completely. Cooling and solidification without crystal formation is called vitrification. The first cryoprotectant solutions able to vitrify at very slow cooling rates while still being compatible with whole organ survival were developed in the late 1990s by cryobiologists Gregory Fahy and Brian Wowk for the purpose of banking transplantable organs. This has allowed animal brains to be vitrified, warmed back up, and examined for ice damage using light and electron microscopy. No ice crystal damage was found; cellular damage was due to dehydration and toxicity of the cryoprotectant solutions.

Costs can include payment for medical personnel to be on call for death, vitrification, transportation in dry ice to a preservation facility, and payment into a trust fund intended to cover indefinite storage in liquid nitrogen and future revival costs. As of 2011, U.S. cryopreservation costs can range from $28,000 to $200,000, and are often financed via life insurance. KrioRus, which stores bodies communally in large dewars, charges $12,000 to $36,000 for the procedure. Some customers opt to have only their brain cryopreserved ("neuropreservation"), rather than their whole body.

As of 2014, about 250 corpses have been cryogenically preserved in the U.S., and around 1,500 people have signed up to have their remains preserved. As of 2016, four facilities exist in the world to retain cryopreserved bodies: three in the U.S. and one in Russia.

A more recent development is Tomorrow Biostasis GmbH, which is a Berlin-based firm offering cryonics and standby and transportation services in Europe. Founded in December 2019 by Emil Kendziorra and Fernando Azevedo Pinheiro, it partners with the European Biostasis Foundation in Switzerland for long-term corpse storage, with their facility completed in 2022.

Considering the lifecycle of corporations, it is extremely unlikely that any cryonics company could continue to exist for sufficient time to take advantage even of the supposed benefits offered: historically, even the most robust corporations have only a one-in-a-thousand chance of surviving even one hundred years. Many cryonics companies have failed;, all but one of the pre-1973 batch had gone out of business, and their stored corpses have been defrosted and disposed of.

Preservation damage
Cryopreservation has long been used by medical laboratories to maintain animal cells, human embryos, and even some organized tissues, for periods as long as three decades. Recovering large animals and organs from a frozen state is however not considered possible at the current level of scientific knowledge. Large vitrified organs tend to develop fractures during cooling, a problem worsened by the large tissue masses and very low temperatures of cryonics. Without cryoprotectants, cell shrinkage and high salt concentrations during freezing usually prevent frozen cells from functioning again after thawing. Ice crystals can also disrupt connections between cells that are necessary for organs to function.

Some cryonics organizations use vitrification without a chemical fixation step, sacrificing some structural preservation quality for less damage at the molecular level. Some scientists, like João Pedro Magalhães, have questioned whether using a deadly chemical for fixation eliminates the possibility of biological revival, making chemical fixation unsuitable for cryonics.

Outside of cryonics firms and cryonics-linked interest groups, many scientists show strong skepticism toward cryonics methods. Cryobiologist Dayong Gao states that "we simply don't know if (subjects have) been damaged to the point where they've 'died' during vitrification because the subjects are now inside liquid nitrogen canisters." Biochemist Ken Storey argues (based on experience with organ transplants) that "even if you only wanted to preserve the brain, it has dozens of different areas, which would need to be cryopreserved using different protocols."

Revival
Revival would require repairing damage from lack of oxygen, cryoprotectant toxicity, thermal stress (fracturing) and freezing in tissues that do not successfully vitrify, finally followed by reversing the cause of death. In many cases, extensive tissue regeneration would be necessary. This revival technology remains speculative and does not currently exist.

Legal issues
Historically, a person had little control regarding how their body was treated after death as religion held jurisdiction over the ultimate fate of their body. However, secular courts began to exercise jurisdiction over the body and use discretion in carrying out of the wishes of the deceased person. Most countries legally treat preserved individuals as deceased persons because of laws that forbid vitrifying someone who is medically alive. In France, cryonics is not considered a legal mode of body disposal; only burial, cremation, and formal donation to science are allowed. However, bodies may legally be shipped to other countries for cryonic freezing. As of 2015, the Canadian province of British Columbia prohibits the sale of arrangements for body preservation based on cryonics. In Russia, cryonics falls outside both the medical industry and the funeral services industry, making it easier in Russia than in the U.S. to get hospitals and morgues to release cryonics candidates.

In London in 2016, the English High Court ruled in favor of a mother's right to seek cryopreservation of her terminally ill 14-year-old daughter, as the girl wanted, contrary to the father's wishes. The decision was made on the basis that the case represented a conventional dispute over the disposal of the girl's body, although the judge urged ministers to seek "proper regulation" for the future of cryonic preservation following concerns raised by the hospital about the competence and professionalism of the team that conducted the preservation procedures. In Alcor Life Extension Foundation v. Richardson, the Iowa Court of Appeals ordered for the disinterment of Richardson, who was buried against his wishes, for cryopreservation.

A detailed legal examination by Jochen Taupitz concludes that cryonic storage is legal in Germany for an indefinite period of time.

Ethics
In 2009, writing in Bioethics, David Shaw examined cryonics. The arguments against it included changing the concept of death, the expense of preservation and revival, lack of scientific advancement to permit revival, temptation to use premature euthanasia, and failure due to catastrophe. Arguments in favor of cryonics include the potential benefit to society, the prospect of immortality, and the benefits associated with avoiding death. Shaw explores the expense and the potential payoff, and applies an adapted version of Pascal's Wager to the question.

In 2016, Charles Tandy wrote in favor of cryonics, arguing that honoring someone's last wishes is seen as a benevolent duty in American and many other cultures.

History
Cryopreservation was applied to human cells beginning in 1954 with frozen sperm, which was thawed and used to inseminate three women. The freezing of humans was first scientifically proposed by Michigan professor Robert Ettinger when he wrote The Prospect of Immortality (1962). In April 1966, the first human body was frozen—though it had been embalmed for two months—by being placed in liquid nitrogen and stored at just above freezing. The middle-aged woman from Los Angeles, whose name is unknown, was soon thawed out and buried by relatives.

The first body to be cryopreserved and then frozen with the hope of future revival was that of James Bedford, claimed by Alcor's Mike Darwin to have occurred within around two hours of his death from cardiorespiratory arrest (secondary to metastasized kidney cancer) on January 12, 1967. Bedford's corpse is the only one frozen before 1974 still preserved today. In 1976, Ettinger founded the Cryonics Institute; his corpse was cryopreserved in 2011. Robert Nelson, "a former TV repairman with no scientific background" who led the Cryonics Society of California, was sued in 1981 for allowing nine bodies to thaw and decompose in the 1970s; in his defense, he claimed that the Cryonics Society had run out of money. This led to the lowered reputation of cryonics in the U.S.

In 2018, a Y-Combinator startup called Nectome was recognized for developing a method of preserving brains with chemicals rather than by freezing. The method is fatal, performed as euthanasia under general anesthesia, but the hope is that future technology would allow the brain to be physically scanned into a computer simulation, neuron by neuron.

Demographics
According to The New York Times, cryonicists are predominantly non-religious white males, outnumbering women by about three to one. According to The Guardian, as of 2008, while most cryonicists used to be young, male, and "geeky", recent demographics have shifted slightly towards whole families.

In 2015, Du Hong, a 61-year-old female writer of children's literature, became the first known Chinese national to have her head cryopreserved.

Reception
Cryonics is generally regarded as a fringe pseudoscience. The Society for Cryobiology rejected members who practiced cryonics, and issued a public statement saying that cryonics is "not science", and that it is a "personal choice" how people want to have their dead bodies disposed of.

Russian company KrioRus is the first non-US vendor of cryonics services. Yevgeny Alexandrov, chair of the Russian Academy of Sciences commission against pseudoscience, said there was "no scientific basis" for cryonics, and that the company's offering was based on "unfounded speculation".

Scientists have expressed skepticism about cryonics in media sources, and the Norwegian philosopher Ole Martin Moen has written that the topic receives a "minuscule" amount of attention from academia.

While some neuroscientists contend that all the subtleties of a human mind are contained in its anatomical structure, few neuroscientists will comment directly upon the topic of cryonics due to its speculative nature. Individuals who intend to be frozen are often "looked at as a bunch of kooks". Cryobiologist Kenneth B. Storey said in 2004 that cryonics is impossible and will never be possible, as cryonics proponents are proposing to "over-turn the laws of physics, chemistry, and molecular science". Neurobiologist Michael Hendricks has said that "Reanimation or simulation is an abjectly false hope that is beyond the promise of technology and is certainly impossible with the frozen, dead tissue offered by the 'cryonics' industry".

Anthropologist Simon Dein writes that cryonics is a typical pseudoscience because of its lack of falsifiability and testability. In Dein's view cryonics is not science, but religion: it places faith in non-existent technology and promises to overcome death itself.

William T. Jarvis has written that "Cryonics might be a suitable subject for scientific research, but marketing an unproven method to the public is quackery".

According to cryonicist Aschwin de Wolf and others, cryonics can often produce intense hostility from spouses who are not cryonicists. James Hughes, the executive director of the pro-life-extension Institute for Ethics and Emerging Technologies, chooses not to personally sign up for cryonics, calling it a worthy experiment but stating laconically that "I value my relationship with my wife."

Cryobiologist Dayong Gao states that "People can always have hope that things will change in the future, but there is no scientific foundation supporting cryonics at this time." While it is universally agreed that "personal identity" is uninterrupted when brain activity temporarily ceases during incidents of accidental drowning (where people have been restored to normal functioning after being completely submerged in cold water for up to 66 minutes), one argument against cryonics is that a centuries-long absence from life might interrupt the conception of personal identity, such that the revived person would "not be themself".

Maastricht University bioethicist David Shaw raises the argument that there would be no point in being revived in the far future if one's friends and families are dead, leaving them all alone; he notes, however, that family and friends can also be frozen, that there is "nothing to prevent the thawed-out freezee from making new friends", and that a lonely existence may be preferable to no existence at all for the revived.

In fiction
Suspended animation is a popular subject in science fiction and fantasy settings. It is often the means by which a character is transported into the future. The characters Philip J. Fry from Futurama and Khan Noonien Singh from Star Trek are prominent examples of this trope.

A survey in Germany found that about half of the respondents were familiar with cryonics, and about half of those familiar with cryonics had learned of the subject from films or television.

In popular culture
The town of Nederland, Colorado, hosts an annual Frozen Dead Guy Days festival to commemorate a substandard attempt at cryopreservation.

Notable people
Corpses subjected to the cryonics process include those of baseball players Ted Williams and his son John Henry Williams (in 2002 and 2004, respectively), engineer and doctor L. Stephen Coles (in 2014), economist and entrepreneur Phil Salin, and software engineer Hal Finney (in 2014).

People known to have arranged for cryonics upon death include PayPal founders Luke Nosek and Peter Thiel, Oxford transhumanists Nick Bostrom and Anders Sandberg, and transhumanist philosopher David Pearce. Larry King previously arranged for cryonics but, according to Inside Edition, later changed his mind.

Disgraced financier and sex offender Jeffrey Epstein wanted to have his head and penis frozen after death so that he could "seed the human race with his DNA".

The corpses of some are mistakenly believed to have undergone cryonics – for instance, the urban legend suggesting Walt Disney's corpse was cryopreserved is false; it was cremated and interred at Forest Lawn Memorial Park Cemetery. Timothy Leary was a long-time cryonics advocate and signed up with a major cryonics provider, but he changed his mind shortly before his death and was not cryopreserved.

title: Cryonics


text:
Unitary patent

The European patent with unitary effect, also known as the unitary patent, is a European patent which benefits from unitary effect in the participating member states of the European Union. Unitary effect may be requested by the proprietor within one month of grant of a European patent, replacing validation of the European patent in the individual countries concerned. Infringement and revocation proceedings are conducted before the Unified Patent Court (UPC), which decisions have a uniform effect for the unitary patent in the participating member states as a whole rather than in each country individually. The unitary patent may be only limited, transferred or revoked, or lapse, in respect of all the participating Member States. Licensing is however possible for part of the unitary territory. The unitary patent may coexist with nationally enforceable patents ("classical" patents) in the non-participating states. The unitary patent's stated aims are to make access to the patent system "easier, less costly and legally secure within the European Union" and "the creation of uniform patent protection throughout the Union".

European patents are granted in English, French, or German and the unitary effect will not require further translations after a transition period. The maintenance fees of the unitary patents are lower than the sum of the renewal fees for national patents of the corresponding area, being equivalent to the combined maintenance fees of Germany, France, the UK and the Netherlands (although the UK is no longer participating following Brexit).

The negotiations which resulted in the unitary patent can be traced back to various initiatives dating to the 1970s. At different times, the project, or very similar projects, have been referred to as the "European Union patent" (the name used in the EU treaties, which serve as the legal basis for EU competency), "EU patent", "Community patent", "European Community Patent", "EC patent" and "COMPAT".

On 17 December 2012, agreement was reached between the European Council and European Parliament on the two EU regulations that made the unitary patent possible through enhanced cooperation at EU level. The legality of the two regulations was challenged by Spain and Italy, but all their claims were rejected by the European Court of Justice. Italy subsequently joined the unitary patent regulation in September 2015, so that all EU member states except Spain and Croatia now participate in the enhanced cooperation for a unitary patent. Unitary effect of newly granted European patents will be available from the date when the related Unified Patent Court Agreement enters into force for those EU countries that have also ratified the UPC, and will extend to those participating member states for which the UPC Agreement enters into force at the time of registration of the unitary patent. Previously granted unitary patents will not automatically get their unitary effect extended to the territory of participating states which ratify the UPC agreement at a later date.

The unitary patent system applies since 1 June 2023, the date of entry into force of the UPC Agreement.

Legislative history

In 2009, three draft documents were published regarding a community patent: a European patent in which the European Community was designated:

 * 1) Council regulation on the community patent,
 * 2) Agreement on the European and Community Patents Court (open to the European Community and all states of the European Patent Convention)
 * 3) Decision to open negotiations regarding this Agreement

Based on those documents, the European Council requested on 6 July 2009 an opinion from the Court of Justice of the European Union, regarding the compatibility of the envisioned Agreement with EU law: "'Is the envisaged agreement creating a Unified Patent Litigation System (currently named European and Community Patents Court) compatible with the provisions of the Treaty establishing the European Community?’"

In December 2010, the use of the enhanced co-operation procedure, under which Articles 326–334 of the Treaty on the Functioning of the European Union provides that a group of member states of the European Union can choose to co-operate on a specific topic, was proposed by twelve Member States to set up a unitary patent applicable in all participating European Union Member States. The use of this procedure had only been used once in the past, for harmonising rules regarding the applicable law in divorce across several EU Member States.

In early 2011, the procedure leading to the enhanced co-operation was reported to be progressing. Twenty-five Member States had written to the European Commission requesting to participate, with Spain and Italy remaining outside, primarily on the basis of ongoing concerns over translation issues. On 15 February, the European Parliament approved the use of the enhanced co-operation procedure for unitary patent protection by a vote of 471 to 160, and on 10 March 2011 the Council gave their authorisation. Two days earlier, on 8 March 2011, the Court of Justice of the European Union had issued its opinion, stating that the draft Agreement creating the European and Community Patent Court would be incompatible with EU law. The same day, the Hungarian Presidency of the Council insisted that this opinion would not affect the enhanced co-operation procedure.

In November 2011, negotiations on the enhanced co-operation system were reportedly advancing rapidly—too fast, in some views. It was announced that implementation required an enabling European Regulation, and a Court agreement between the states that elect to take part. The European Parliament approved the continuation of negotiations in September. A draft of the agreement was issued on 11 November 2011 and was open to all member states of the European Union, but not to other European Patent Convention states. However, serious criticisms of the proposal remained mostly unresolved. A meeting of the Competitiveness Council on 5 December failed to agree on the final text. In particular, there was no agreement on where the Central Division of a Unified Patent Court should be located, "with London, Munich and Paris the candidate cities."

The Polish Presidency acknowledged on 16 December 2011 the failure to reach an agreement "on the question of the location of the seat of the central division." The Danish Presidency therefore inherited the issue. According to the President of the European Commission in January 2012, the only question remaining to be settled was the location of the Central Division of the Court. However, evidence presented to the UK House of Commons European Scrutiny Committee in February suggested that the position was more complicated. At an EU summit at the end of January 2012, participants agreed to press on and finalise the system by June. On 26 April, Herman Van Rompuy, President of the European Council, wrote to members of the council, saying "This important file has been discussed for many years and we are now very close to a final deal,.... This deal is needed now, because this is an issue of crucial importance for innovation and growth. I very much hope that the last outstanding issue will be sorted out at the May Competitiveness Council. If not, I will take it up at the June European Council." The Competitiveness Council met on 30 May and failed to reach agreement.

A compromise agreement on the seat(s) of the unified court was eventually reached at the June European Council (28–29 June 2012), splitting the central division according to technology between Paris (the main seat), London and Munich. However, on 2 July 2012, the European Parliament decided to postpone the vote following a move by the European Council to modify the arrangements previously approved by MEPs in negotiations with the European Council. The modification was considered controversial and included the deletion of three key articles (6–8) of the legislation, seeking to reduce the competence of the European Union Court of Justice in unitary patent litigation. On 9 July 2012, the Committee on Legal Affairs of the European Parliament debated the patent package following the decisions adopted by the General Council on 28–29 June 2012 in camera in the presence of MEP Bernhard Rapkay. A later press release by Rapkay quoted from a legal opinion submitted by the Legal Service of the European Parliament, which affirmed the concerns of MEPs to approve the decision of a recent EU summit to delete said articles as it "nullifies central aspects of a substantive patent protection". A Europe-wide uniform protection of intellectual property would thus not exist with the consequence that the requirements of the corresponding EU treaty would not be met and that the European Court of Justice could therefore invalidate the legislation. By the end of 2012 a new compromise was reached between the European Parliament and the European Council, including a limited role for the European Court of Justice. The Unified Court will apply the Unified Patent Court Agreement, which is considered national patent law from an EU law point of view, but still is equal for each participant. [However the draft statutory instrument aimed at implementation of the Unified Court and UPC in the UK provides for different infringement laws for: European patents (unitary or not) litigated through the Unified Court; European patents (UK) litigated before UK courts; and national patents]. The legislation for the enhanced co-operation mechanism was approved by the European Parliament on 11 December 2012 and the regulations were signed by the European Council and European Parliament officials on 17 December 2012.

On 30 May 2011, Italy and Spain challenged the council's authorisation of the use of enhanced co-operation to introduce the trilingual (English, French, German) system for the unitary patent, which they viewed as discriminatory to their languages, with the CJEU on the grounds that it did not comply with the EU treaties. In January 2013, Advocate General Yves Bot delivered his recommendation that the court reject the complaint. Suggestions by the Advocate General are advisory only, but are generally followed by the court. The case was dismissed by the court in April 2013, however Spain launched two new challenges with the EUCJ in March 2013 against the regulations implementing the unitary patent package. The court hearing for both cases was scheduled for 1 July 2014. Advocate-General Yves Bot published his opinion on 18 November 2014, suggesting that both actions be dismissed ( and ). The court handed down its decisions on 5 May 2015 as and  fully dismissing the Spanish claims. Following a request by its government, Italy became a participant of the unitary patent regulations in September 2015.

European patents
European patents are granted in accordance with the provisions of the European Patent Convention (EPC), via a unified procedure before the European Patent Office (EPO). While upon filing of a European patent application, all 39 Contracting States are automatically designated, a European patent becomes a bundle of "national" European patents upon grant. In contrast to the unified character of a European patent application, a granted European patent has, in effect, no unitary character, except for the centralized opposition procedure (which can be initiated within 9 months from grant, by somebody else than the patent proprietor), and the centralized limitation and revocation procedures (which can only be instituted by the patent proprietor). In other words, a European patent in one Contracting State, i.e. a "national" European patent, is effectively independent of the same European patent in each other Contracting State, except for the opposition, limitation and revocation procedures. The enforcement of a European patent is dealt with by national law. The abandonment, revocation or limitation of the European patent in one state does not affect the European patent in other states.

While the EPC already provided the possibility for a group of member states to allow European patents to have a unitary character also after grant, until now, only Liechtenstein and Switzerland have opted to create a unified protection area (see Unitary patent (Switzerland and Liechtenstein)).

By requesting unitary effect within one month of grant, the patent proprietor is now able to obtain uniform protection in the participating members states of the European Union in a single step, considerably simplifying obtaining patent protection in a large part of the EU. The unitary patent system co-exists with national patent systems and European patent without unitary effects. The unitary patent does not cover EPC countries that are not member of the European Union, such as UK or Turkey.

Legal basis and implementation
The implementation of the unitary patent is based on three legal instruments:
 * Regulation of the European Parliament and of the Council implementing enhanced co-operation in the area of the creation of unitary patent protection
 * Council Regulation implementing enhanced co-operation in the area of the creation of unitary patent protection with regard to the applicable translation arrangements
 * Agreement on a Unified Patent Court

Thus the unitary patent is based on EU law as well as the European Patent Convention (EPC). provides the legal basis for establishing a common system of patents for Parties to the EPC. Previously, only Liechtenstein and Switzerland had used this possibility to create a unified protection area (see Unitary patent (Switzerland and Liechtenstein)).

Regulations regarding the unitary patent
The first two regulations were approved by the European Parliament on 11 December 2012, with future application set for the 25 member states then participating in the enhanced cooperation for a unitary patent (all then EU member states except Croatia, Italy and Spain). The instruments were adopted as regulations EU 1257/2012 and 1260/2012 on 17 December 2012, and entered into force in January 2013. Following a request by its government, Italy became a participant of the unitary patent regulations in September 2015.

As of March 2022, neither of the two remaining non-participants in the unitary patent (Spain and Croatia) had requested the European Commission to participate.

Although formally the Regulations will apply to all 25 participating states from the moment the UPC Agreement enters into force for the first group of ratifiers, the unitary effect of newly granted unitary patents will only extend to those of the 25 states where the UPC Agreement has entered into force, while patent coverage for other participating states without UPC Agreement ratification will be covered by a coexisting normal European patent in each of those states.

The unitary effect of unitary patents means a single renewal fee, a single ownership, a single object of property, a single court (the Unified Patent Court) and uniform protection, which means that revocation as well as infringement proceedings are to be decided for the unitary patent as a whole rather than for each country individually. Licensing is however to remain possible for part of the unitary territory.

Role of the European Patent Office
Some administrative tasks relating to the European patents with unitary effect are performed by the European Patent Office, as authorized by. These tasks include the collection of renewal fees and registration of unitary effect upon grant, recording licenses and statements that licenses are available to any person. Decisions of the European Patent Office regarding the unitary patent are open to appeal to the Unified Patent Court, rather than to the EPO Boards of Appeal.

Translation requirements for the European patent with unitary effect
For a unitary patent, ultimately no translation will be required (except under certain circumstances in the event of a dispute ), which is expected to significantly reduce the cost for protection in the whole area. However, Article 6 of Regulation 1260/2012 provides that, during a transitional period of minimum six years and no more than twelve years, one translation needs to be provided. Namely, a full translation of the European patent specification needs to be provided either into English if the language of the proceedings at the EPO was French or German, or into any other EU official language if the language of the proceedings at the EPO was English. Such translation will have no legal effect and will be "for information purposes only”. In addition, machine translations will be provided, which will be, in the words of the regulation, "for information purposes only and should not have any legal effect".

Comparison with the current translation requirements for traditional bundle European patents
In several EPC contracting states, for the national part of a traditional bundle European patent (i.e., for a European patent without unitary effect), a translation has to be filed within a three-month time limit after the publication of grant in the European Patent Bulletin under, otherwise the patent is considered never to have existed (void ab initio) in that state. For the 22 parties to the London Agreement, this requirement has already been abolished or reduced (e.g. by dispensing with the requirement if the patent is available in English, and/or only requiring translation of the claims).

Translation requirements for the participating states in the enhanced cooperation for a unitary patent are shown below:

Unitary patent as an object of property
Article 7 of Regulation 1257/2012 provides that, as an object of property, a European patent with unitary effect will be treated "in its entirety and in all participating Member States as a national patent of the participating Member State in which that patent has unitary effect and in which the applicant had her/his residence or principal place of business or, by default, had a place of business on the date of filing the application for the European patent." When the applicant had no domicile in a participating Member State, German law will apply. Ullrich has the criticized the system, which is similar to the Community Trademark and the Community Design, as being "in conflict with both the purpose of the creation of unitary patent protection and with primary EU law."

Agreement on a Unified Patent Court
The Agreement on a Unified Patent Court provides the legal basis for the Unified Patent Court (UPC): a patent court for European patents (with and without unitary effect), with jurisdiction in those countries where the Agreement is in effect. In addition to regulations regarding the court structure, it also contains substantive provisions relating to the right to prevent use of an invention and allowed use by non-patent proprietors (e.g. for private non-commercial use), preliminary and permanent injunctions. Entry into force for the UPC took place after Germany deposited its instrument of ratification of the UPC Agreement, which triggered the countdown until the Agreement's entry into force on June 1, 2023.

Parties
The UPC Agreement was signed on 19 February 2013 by 24 EU member states, including all states then participating in the enhanced co-operation measures except Bulgaria and Poland. Bulgaria signed the agreement on 5 March 2013 following internal administrative procedures. Italy, which did not originally join the enhanced co-operation measures but subsequently signed up, did sign the UPC agreement. The agreement remains open to accession for all remaining EU member states, with all European Union Member States except Spain and Poland having signed the Agreement. States which do not participate in the unitary patent regulations can still become parties to the UPC agreement, which would allow the new court to handle European patents validated in the country.

On 18 January 2019, Kluwer Patent Blog wrote, "a recurring theme for some years has been that 'the UPC will start next year'". Then, Brexit and German constitutional court complaint were considered as the main obstacles. The German constitutional court first decided in a decision of 13 February 2020 against the German ratification of the Agreement on the ground that the German Parliament did not vote with the required majority (2/3 according to the judgement). After a second vote and further, this time unsuccessful, constitutional complaints, Germany formally ratified the UPC Agreement on 7 August 2021. While the UK ratified the agreement in April 2018, the UK later withdrew from the Agreement following Brexit.

As of the entry into force of the UPC on 1 June 2023, 17 countries had ratified the Agreement. Romania ratified the agreement in May 2024, and will join as the 18th participating member on 1 September 2024.

Jurisdiction
The Unified Patent Court has exclusive jurisdiction in infringement and revocation proceedings involving European patents with unitary effect, and during a transition period non-exclusive jurisdiction regarding European patents without unitary effect in the states where the Agreement applies, unless the patent proprietor decides to opt out. It furthermore has jurisdiction to hear cases against decisions of the European Patent Office regarding unitary patents. As a court of several member states of the European Union it may (Court of First Instance) or must (Court of Appeal) ask prejudicial questions to the European Court of Justice when the interpretation of EU law (including the two unitary patent regulations, but excluding the UPC Agreement) is not obvious.

Organization
The court has two instances: a court of first instance and a court of appeal. The court of appeal and the registry have their seats in Luxembourg, while the central division of the court of first instance would have its seat in Paris. The central division has a thematic branch in Munich (the London location has yet to be replaced by a new location within the EU). The court of first instance may further have local and regional divisions in all member states that wish to set up such divisions.

Geographical scope of and request for unitary effect
While the regulations formally apply to all 25 member states participating in the enhanced cooperation for a unitary patent, from the date the UPC agreement has entered into force for the first group of ratifiers, unitary patents will only extend to the territory of those participating member states where the UPC Agreement had entered into force when the unitary effect was registered. If the unitary effect territory subsequently expands to additional participating member states for which the UPC Agreement later enters into force, this will be reflected for all subsequently registered unitary patents, but the territorial scope of the unitary effect of existing unitary patents will not be extended to these states.

Unitary effect can be requested up to one month after grant of the European patent directly at the EPO, with retroactive effect from the date of grant. However, according to the Draft Rules Relating to Unitary Patent Protection, unitary effect would be registered only if the European patent has been granted with the same set of claims for all the 25 participating member states in the regulations, whether the unitary effect applies to them or not. European patents automatically become a bundle of "national" European patents upon grant. Upon the grant of unitary effect, the "national" European patents will retroactively be considered to never have existed in the territories where the unitary patent has effect. The unitary effect does not affect "national" European patents in states where the unitary patent does not apply. Any "national" European patents applying outside the "unitary effect" zone will co-exist with the unitary patent.

Special territories of participating member states
As the unitary patent is introduced by an EU regulation, it is expected to not only be valid in the mainland territory of the participating member states that are party to the UPC, but also in those of their special territories that are part of the European Union. As of April 2014, this includes the following fourteen territories:

 * Cyprus: UN Buffer Zone
 * Finland: Åland
 * France: French Guiana, Guadeloupe, Martinique, Mayotte, Réunion, Saint Martin
 * Germany: Büsingen am Hochrhein, Helgoland
 * Greece: Mount Athos
 * Portugal: Azores, Madeira

In addition to the territories above, the European Patent Convention has been extended by two member states participating in the enhanced cooperation for a unitary patent to cover some of their dependent territories outside the European Union: In following of those territories, the unitary patent is de facto extended through application of national (French, or Dutch) law:

 * France: French Southern and Antarctic Lands, Saint Barthélemy, Saint-Pierre and Miquelon and Wallis and Futuna
 * Netherlands: Caribbean Netherlands, Curaçao, Sint Maarten

However, the unitary patent does not apply in the French territories French Polynesia and New Caledonia as implementing legislation would need to be passed by those jurisdictions (rather than the French national legislation required in the other territories) and this has not been done.

Costs
The renewal fees are planned to be based on the cumulative renewal fees due in the four countries where European patents were most often validated in 2015 (Germany, France, the UK and the Netherlands). This is despite the UK leaving the unitary patent system following Brexit. The renewal fees of the unitary patent would thus be ranging from 35 Euro in the second year to 4855 in the 20th year. The renewal fees will be collected by the EPO, with the EPO keeping 50% of the fees and the other 50% being redistributed to the participating member states.

Translation requirements as well as the requirement to pay yearly patent maintenance fees in individual countries presently renders the European patent system costly to obtain protection in the whole of the European Union.

In an impact assessment from 2011, the European Commission estimated that the costs of obtaining a patent in all 27 EU countries would drop from over 32 000 euro (mainly due to translation costs) to 6 500 euro (for the combination of an EU, Spanish and Italian patent) due to introduction of the Unitary patent. Per capita costs of an EU patent were estimated at just 6 euro/million in the original 25 participating countries (and 12 euro/million in the 27 EU countries for protection with a Unitary, Italian and Spanish patent).

How the EU Commission has presented the expected cost savings has however been sharply criticized as exaggerated and based on unrealistic assumptions. The EU Commission has notably considered the costs for validating a European patent in 27 countries while in reality only about 1% of all granted European patents are currently validated in all 27 EU states. Based on more realistic assumptions, the cost savings are expected to be much lower than actually claimed by the commission. For example, the EPO calculated that for an average EP patent validated and maintained in 4 countries, the overall savings to be between 3% and 8%.

Statistics
During the first year of the unitary patent, that is, from June 1, 2023 to May 31, 2024, more than 27500 European patents with unitary effect have been registered. This corresponds to almost a quarter of all European patents granted during that period.

1970s and 1980s: proposed Community Patent Convention
Work on a Community patent started in the 1970s, but the resulting Community Patent Convention (CPC) was a failure.

The "Luxembourg Conference on the Community Patent" took place in 1975 and the Convention for the European Patent for the common market, or (Luxembourg) Community Patent Convention (CPC), was signed at Luxembourg on 15 December 1975, by the 9 member states of the European Economic Community at that time. However, the CPC never entered into force. It was not ratified by enough countries.

Fourteen years later, the Agreement relating to Community patents was made at Luxembourg on 15 December 1989. It attempted to revive the CPC project, but also failed. This Agreement consisted of an amended version of the original Community Patent Convention. Twelve states signed the Agreement: Belgium, Denmark, France, Germany, Greece, Ireland, Italy, Luxembourg, the Netherlands, Portugal, Spain, and United Kingdom. All of those states would need to have ratified the Agreement to cause it to enter into force, but only seven did so: Denmark, France, Germany, Greece, Luxembourg, the Netherlands, and United Kingdom.

Nevertheless, a majority of member states of the EEC at that time introduced some harmonisation into their national patent laws in anticipation of the entry in force of the CPC. A more substantive harmonisation took place at around the same time to take account of the European Patent Convention and the Strasbourg Convention.

2000 to 2004: EU Regulation proposal
In 2000, renewed efforts from the European Union resulted in a Community Patent Regulation proposal, sometimes abbreviated as CPR. It provides that the patent, once it has been granted by the European Patent Office (EPO) in one of its procedural languages (English, German or French) and published in that language, with a translation of the claims into the two other procedural languages, will be valid without any further translation. This proposal is aimed to achieve a considerable reduction in translation costs.

Nevertheless, additional translations could become necessary in legal proceedings against a suspected infringer. In such a situation, a suspected infringer who has been unable to consult the text of the patent in the official language of the Member State in which he is domiciled, is presumed, until proven otherwise, not to have knowingly infringed the patent. To protect a suspected infringer who, in such a situation, has not acted in a deliberate manner, it is provided that the proprietor of the patent will not be able to obtain damages in respect of the period prior to the translation of the patent being notified to the infringer.

The proposed Community Patent Regulation should also establish a court holding exclusive jurisdiction to invalidate issued patents; thus, a Community Patent's validity will be the same in all EU member states. This court will be attached to the present European Court of Justice and Court of First Instance through use of provisions in the Treaty of Nice.

Discussion regarding the Community patent had made clear progress in 2003 when a political agreement was reached on 3 March 2003. However, one year later in March 2004 under the Irish presidency, the Competitiveness Council failed to agree on the details of the Regulation. In particular the time delays for translating the claims and the authentic text of the claims in case of an infringement remained problematic issues throughout discussions and in the end proved insoluble.

In view of the difficulties in reaching an agreement on the community patent, other legal agreements have been proposed outside the European Union legal framework to reduce the cost of translation (of patents when granted) and litigation, namely the London Agreement, which entered into force on 1 May 2008—and which has reduced the number of countries requiring translation of European patents granted nowadays under the European Patent Convention, and the corresponding costs to obtain a European patent —and the European Patent Litigation Agreement (EPLA), a proposal that has now lapsed.

Reactions to the failure
After the council in March 2004, EU Commissioner Frits Bolkestein said that "The failure to agree on the Community Patent I am afraid undermines the credibility of the whole enterprise to make Europe the most competitive economy in the world by 2010." Adding:

"It is a mystery to me how Ministers at the so-called 'Competitiveness Council' can keep a straight face when they adopt conclusions for the Spring European Council on making Europe more competitive and yet in the next breath backtrack on the political agreement already reached on the main principles of the Community Patent in March of last year. I can only hope that one day the vested, protectionist interests that stand in the way of agreement on this vital measure will be sidelined by the over-riding importance and interests of European manufacturing industry and Europe's competitiveness. That day has not yet come."

Jonathan Todd, Commission's Internal Market spokesman, declared: "Normally, after the common political approach, the text of the regulation is agreed very quickly. Instead, some Member States appear to have changed their positions. (...) It is extremely unfortunate that European industry's competitiveness, innovation and R&D are being sacrificed for the sake of preserving narrow vested interests."

European Commission President Romano Prodi, asked to evaluate his five-year term, cited as his weak point the failure of many EU governments to implement the "Lisbon Agenda", agreed in 2001. In particular, he cited the failure to agree on a Europewide patent, or even the languages to be used for such a patent, "because member states did not accept a change in the rules; they were not coherent".

Since 2005: stalemate and new debate

Thus, in 2005, the Community patent looked unlikely to be implemented in the near future. However, on 16 January 2006 the European Commission "launched a public consultation on how future action in patent policy to create an EU-wide system of protection can best take account of stakeholders' needs." The Community patent was one of the issues the consultation focused on. More than 2500 replies were received. According to the European Commission, the consultation showed that there is widespread support for the Community patent but not at any cost, and "in particular not on the basis of the Common Political Approach reached by EU Ministers in 2003".

In February 2007, EU Commissioner Charlie McCreevy was quoted as saying: "The proposal for an EU-wide patent is stuck in the mud. It is clear to me from discussions with member states that there is no consensus at present on how to improve the situation."

The European Commission released a white paper in April 2007 seeking to "improve the patent system in Europe and revitalise the debate on this issue." On 18 April 2007, at the European Patent Forum in Munich, Germany, Günter Verheugen, Vice-President of the European Commission, said that his proposal to support the European economy was "to have the London Agreement ratified by all member states, and to have a European patent judiciary set up, in order to achieve rapid implementation of the Community patent, which is indispensable". He further said that he believed this could be done within five years.

In October 2007, the Portuguese presidency of the Council of the European Union proposed an EU patent jurisdiction, "borrowing heavily from the rejected draft European Patent Litigation Agreement (EPLA)". In November 2007, EU ministers were reported to have made some progress towards a community patent legal system, with "some specific results" expected in 2008.

In 2008, the idea of using machine translations to translate patents was proposed to solve the language issue, which is partially responsible for blocking progress on the community patent. Meanwhile, European Commissioner for Enterprise and Industry Günter Verheugen declared at the European Patent Forum in May 2008 that there was an "urgent need" for a community patent.

Agreement in December 2009, and language issue
In December 2009, it was reported that the Swedish EU presidency had achieved a breakthrough in negotiations concerning the community patent. The breakthrough was reported to involve setting up a single patent court for the EU, however ministers conceded much work remained to be done before the community patent would become a reality.

According to the agreed plan, the EU would accede to the European Patent Convention as a contracting state, and patents granted by the European Patent Office will, when validated for the EU, have unitary effect in the territory of the European Union. On 10 November 2010, it was announced that no agreement had been reached and that, "in spite of the progress made, [the Competitiveness Council of the European Union had] fallen short of unanimity by a small margin," with commentators reporting that the Spanish representative, citing the aim to avoid any discrimination, had "re-iterated at length the stubborn rejection of the Madrid Government of taking the 'Munich' three languages regime (English, German, French) of the European Patent Convention (EPC) as a basis for a future EU Patent."

title: Unitary patent


text:
Cistron

A cistron is a region of DNA that is conceptually equivalent to some definitions of a gene, such that the terms are synonymous from certain viewpoints, especially with regard to the molecular gene as contrasted with the Mendelian gene. The question of which scope of a subset of DNA (that is, how large a segment of DNA) constitutes a unit of selection is the question that governs whether cistrons are the same thing as genes. The word cistron is used to emphasize that molecular genes exhibit a specific behavior in a complementation test (cis-trans test); distinct positions (or loci) within a genome are cistronic.

History
The words cistron and gene were coined before the advancing state of biology made it clear to many people that the concepts they refer to, at least in some senses of the word gene, are either equivalent or nearly so. The same historical naming practices are responsible for many of the synonyms in the life sciences.

The term cistron was coined by Seymour Benzer in an article entitled The elementary units of heredity. The cistron was defined by an operational test applicable to most organisms that is sometimes referred to as a cis-trans test, but more often as a complementation test.

Richard Dawkins in his influential book The Selfish Gene argues against the cistron being the unit of selection and against it being the best definition of a gene. (He also argues against group selection.) He doesn't argue against the existence of cistrons, or their being elementary, but rather against the idea that natural selection selects them; he argues that it used to, back in earlier eras of life's development, but not anymore. He defines a gene as a larger unit, which others may now call gene clusters, as the unit of selection. He also defines replicators, more general than cistrons and genes, in this gene-centered view of evolution.

Definition
Defining a Cistron as a segment of DNA coding for a polypeptide, the structural gene in a transcription unit could be said as monocistronic (mostly in eukaryotes) or polycistronic (mostly in bacteria and prokaryotes). For example, suppose a mutation at a chromosome position $$x$$ is responsible for a change in recessive trait in a diploid organism (where chromosomes come in pairs). We say that the mutation is recessive because the organism will exhibit the wild type phenotype (ordinary trait) unless both chromosomes of a pair have the mutation (homozygous mutation). Similarly, suppose a mutation at another position, $$y$$, is responsible for the same recessive trait. The positions $$x$$ and $$y$$ are said to be within the same cistron when an organism that has the mutation at $$x$$ on one chromosome and has the mutation at position $$y$$ on the paired chromosome exhibits the recessive trait even though the organism is not homozygous for either mutation. When instead the wild type trait is expressed, the positions are said to belong to distinct cistrons / genes. Or simply put, mutations on the same cistrons will not complement; as opposed to mutations on different cistrons may complement (see Benzer's T4 bacteriophage experiments T4 rII system).

For example, an operon is a stretch of DNA that is transcribed to create a contiguous segment of RNA, but contains more than one cistron / gene. The operon is said to be polycistronic, whereas ordinary genes are said to be monocistronic.

title: Cistron