text:
Talk:Computer multitasking

not imply unix was always multitasking
Removed: "UNIX, designed as a "single user" operating system in the 1970s, included most of the multitasking capabilities of its multi-user cousin MULTIX, and is today used for both purposes." Bad example because it is mostly untrue. Unix was very briefly a single user system, but got both multi-user and multi-tasking features very early, and at about the same time.
 * Perhaps we could find a better example of multitasking being recognized as a useful feature even in a single user OS, such as a PC OS? Paragraph 8 ("Although the original purpose behind the design...") would be a good place for it. --D

 * Excellent example as UNIX was designed to be the single user version of the already existing MULTIX - the name reflects this (uniX vs. multiX) - the fact that it later became a multiprogramming, even later a parallel processing OS in some versions, doesn't change the fact, that it originally was single user single task sys., the purpose of which was playing games on the DEC PDP 7. Later hype tries to deny this fact, same as later hype tries to postulate that Gates (at times: and Allen) designed DOS, which they in fact bought ready made from Seattle Computer. Let's kill myths. John.St (talk) 11:45, 7 June 2011 (UTC)

thnx —Preceding unsigned comment added by 122.169.66.171 (talk) 06:27, 3 April 2010 (UTC)

change wording not imply ordering
"To remedy this situation, most time-sharing systems quickly evolved a more advanced approach known as [preemptive multitasking]?. "

In context, this reads like preemptive multitasking developed after cooperative multitasking. Preemptive multitasking was tried in the early 1960s, but it turned out to be a lot harder to do reliably than anyone expected. Remember that back then, people routinely made I/O calls from applications and grabbing control away from somebody who had just issued a read to a paper tape reader often didn't work out all that well. I'm pretty sure that cooperative multitasking was a kludge to make multitasking work better by making sure that programs were in a suspendable state when they gave up control.

I'm not sure, however, whether a change is needed or will be an improvement. - DJK

multitasking vs multiprogramming vs time sharing
It seems those three notions are intermixed here. A clarification is needed.

 * Multitasking is a generic term allowing multiple tasks to be run, without regard to timing.

 * Multiprogramming is the possibility for multiple programs to be ready, and waiting for the processor to be free. The initial purpose of this was to allow a second program to run while the first one waited for some I/O to complete. Multiprogramming does not require any cooperation between programs, as there were no interactive users anyway. If a program needed the CPU for a long time, it could use it.

 * Time sharing is a method where all ready tasks are given a fair access to the CPU.

 * It should be noted that, multi-tasking (aka time-sharing) is a type of multi-programming. A multi-programming system is not a type of multi-tasking system however.

 * Multi-programming was put in place to keep the CPU busy, and not waiting on IO while it could be serving other processes.

The goal of multiprogramming is to minimize idle time for the processor, and that was the primary objective in the times the processor time was expensive.

reading from a tape
"(e.g. reading from a tape)" ?? Dated? In a modern computer would this be comparable to reading from a drive or waiting for a result from memory or an external device? - Omegatron 18:06, Oct 13, 2004 (UTC)

Suggestion: Give options: Reading from a disk drive, reading from a tape, reading from a terminal/keyboard. — Preceding unsigned comment added by 208.127.217.116 (talk) 23:09, 6 April 2017 (UTC)

 * Done. (I also added "receiving a message from a network". Guy Harris (talk) 00:51, 7 April 2017 (UTC)

Merge from co-operative multitasking
weak disagree : I'd suggest that rather than merging, just add a "main article" link, as it could be argued that co-operative multitasking is a valid and reasonable article in it's own right. Guinness 11:31, 15 December 2005 (UTC)

agree : There's not a substantial amount of content in the separate article. I'd suggest that it be merged, and only split it if it later gets big enough. Currently it's mostly just redundant, and the little that's not is split across two articles. QuiTeVexat 05:59, 20 December 2005 (UTC)

observation: Preemption (computing) appears to describe the same thing also. I'm not familiar with the procedures around here, so I leave it to someone else to tag it. -- G. Gearloose (?!) 01:04, 5 February 2006 (UTC)

 * I am suggesting merging preemption into deadlock. The problem is, preemptive multitasking and preemption of resources aren't exactly the same thing, although they are related.  Also, I'm not sure a full article can be written on just preemption.  Perhaps a split is a better choice? MagiMaster 09:04, 10 July 2006 (UTC)

Can you explain what you mean by "preemption of resources"? --Chris Purcell 17:00, 10 July 2006 (UTC)

Merge from Co-operative multitasking and Preemption (computing)
The discussion at Talk:Deadlock seems to have generated a consensus against merging. The discussion here seems to have fizzled out without it being really clear if there is a consensus. Since both of the other articles are hardly longer than the sections here and don't look like growing (in my opinion) I would propose going ahead and merging those two articles into this article. This would also help remove the Merge backlog. Any objections? --Boson 21:52, 19 October 2006 (UTC)

I/O bound / CPU bound
Surely the terms "I/O bound" and "CPU bound" aren't states of processes, but properties of a program (or a portion thereof)? (Adjectvies where a

An I/O bound process may be time-limited by the speed of its I/O, but when it cannot continue until I/O occurs then it is "blocked", whether or not it's in a busy wait. If it's waiting for a signal rather than polling, then I'd call that "waiting".

Similarly a CPU bound process is "running" (or "on the CPU"), or if not, then it's "ready".

Multithreading
"Fibers are even more lightweight than threads, and somewhat easier to program with, although they tend to lose some or all of the benefits of threads on machines with multiple processors."

There is no reference to the advantages and disadvantages of multiple cores or processers in a multitreading system, and whether multiple cores benefit or hinder other types of multitasking. This is rather important with the current surge in development of multicore processors. I don't have enough knowledge of or experience with multicore systems to edit the article - can anyone else contribute to this? --[smiler] 06:33, 16 February 2006 (UTC)

 * I also wonder exactly what this means, I added the citation needed template 222.225.196.13 03:06, 1 August 2007 (UTC)

how could a system be designed to allow a choice of operating systems to boot from
how could a system be designed to allow a choice of operating systems to boot from?

 * Typical multi-booting systems have a second-stage boot loader. On a PC, the second-stage boot loader sits in the MBR, and gets loaded by the BIOS.
 * Or you can replace the boot device -- easy if that is removable. In older computers (pre-PC) that was often true. Paul Koning (talk) 16:09, 4 November 2015 (UTC)

Please specify
"One use for interrupts is to allow a simpler processor to simulate the dedicated I/O processors that it does not have."

I don't understand. A processor simpler than what (central or I/O?) is using interrupts to simulate the I/O processors?! —Preceding unsigned comment added by Doru001 (talk • contribs) 09:15, 16 April 2008 (UTC)
 * I know what this sentence was supposed to mean, but it is completely off-topic here. See channel I/O. Deleted it. ✅ --Kubanczyk (talk) 20:47, 2 July 2008 (UTC)

Amiga
I added the note on the Amiga, it seems the guys who really care about this article are not aware that there was a computer called the Amiga (most peopel think of the Amiga as a video game machine, but to those who actually used them for serious media work know better)..

There are books on the low-level programming of the system, and reading them you will realize it was a truly pre-emptive multi-tasker, and it was mentioned a lot of times by the userbase themselves, it had task priorities, it's where the eurodemos that exploit the features of the Amiga got their start.

The reason it crashed a lot and gave GURU errors was that it was expected of the developers to write their programs by the rules that Commodore laid out, and if anyone failed to manage their resources properly, the machine would crash (the result of the CPU executing beyond the code block or writing data into a code block).

This could be seen as a failure from one perspective, but from another code-purist point of view, it forced coders to write correct code that behaved and managed it's resources. If a language like java (but not as bureaucratic) had been used on the Amiga, it would not have crashed because of the elimination of pointers. It was because of the improper use of pointers and sloppiness of that coders that wrote for it, that it crashed.

To use an MPU, is to make the statement that humans are not perfect, so we should not expect to be able to write correct code either. Even when Windows 98 and Mac had MPU's, they would crash.. And computers still crash.. So in hind-sight, was the Amiga so wrong for the way it was designed, or was it more correct than any computer that has been developed since? BTW, Deluxe Paint 3 for the Amiga 1000 was around 300KB, and would run within 512KB with the Workbench and enough memory to paint pictures. When Apple attempted to make a competitor for the Amiga, they came up with the Apple IIgs (15 voice ensoniq chip with 64KB of memory and a, what was it? 1Mhz processor). And still people worship Apple like they make really good technology, look at history guyz, don't rewrite it..

97.123.57.99 (talk) 07:59, 11 August 2009 (UTC)

I removed the bit about the Amiga because it wasn't neutral, it referenced no sources, and was obvious boosterism by a fan of the Amiga. Not to disparage the Amiga in any way, but the discussions of when consumer operating systems offered preemptive multitasking is somewhat tangential to the topic, and is likely mentioned in the specific articles about those operating systems. Since Windows and MacOS are still widely used it might give some context for people who remember those days, so I left those. Even those aren't vital, really. Better to drop even the Windows and MacOS mentions rather than have a sentence for every introduction of a consumer product which in some way advanced multitasking. If people would like to do some research, perhaps they can find some instances of products which illustrate real-time multitasking systems, which currently has no such examples.

--Charles 2/20/2011 —Preceding unsigned comment added by 74.96.54.208 (talk) 22:05, 20 February 2011 (UTC)

Alternating Multitasking
I was thinking should this topic contain topics on Alternating Multitasking, the term is not commonly used, but it describes a SIMD array processors, in which the processor tried do schedule 2 task at once by alternating sequence. So if there is 2 task, Work A and Work B. The sequences would be A, B, A, B, where task is A work, stop, work, stop. The concept is based on, overlapping the time between Task A stop and Time B work.

I know OCZ Enhanced Bandwidth and IBM Power Architecture threading uses this mechanism. Except IBM, does it a bit differently, because the instruction are very long that involves, prepare the query, fetch...etc. The time between preparition of thread is overlapped by implanting a XDR RAM. It is not really a true alternation method, but it achieve by the following
 * Since it is slower at preparing threads (in Data cache), it implants a XDR RAM so it can (use that time to prepare for instruction cache and decoding) therefore the total wasted (or buffer) time is not wasted.

The only problem is that the speed that XDR RAM is not enough so it can only reach 1 petaFLOPS (or roughly tenfold) instead of at a more scalable multiple.

Usually when components are doing Alternation, it is best when one rate is faster than the order. --Ramu50 (talk) 01:45, 7 October 2008 (UTC)

Nice Article
Just want to thank everyone involved in writing this article. It's well-organized and concise, so I quickly got a good overview of the topic. Reads pretty well too, with consistent voice throughout. --Armchair info guy (talk) 03:00, 1 March 2009 (UTC)
 * Hear, hear! Came here to say thank you for the great article, and someone already did it before! I wish all articles were such well written and to the point. Great article! Thank you! WillNess (talk) 19:35, 12 July 2011 (UTC)

Preemption overhead vs cooperative?
I expect that there is a certain amount of processing overhead that comes from designing a preemptive OS, due to needing to allow for a management layer that can schedule, prioritize, or idle other processes.

But I don't know if this is really true or not. It seems difficult to do an apples-to-apples performance comparison between a preemptive and a cooperative OS to know if the cooperative can use CPU cycles more efficiently by not having the management layer.

DMahalko (talk) 03:58, 3 June 2009 (UTC)

Theoretically I think there can be a very significant efficiency advantage to a cooperatively scheduled system, because of the avoidance of locking.

In a preemptively scheduled system, whenever a thread uses a shared resource (that other threads could use), it must use some mechanism of exclusion to ensure that use of the resource is not chaotically split between threads. The mechanism usually used is locking, and this typically entails significant overhead.

In theory, in a cooperatively scheduled system, threads can avoid this overhead by yielding only at times in between using shared resources. However, I say 'in theory' because in reality it is quite often the case that this is impractical. Either there would be (potentially) an unacceptably long wait between yields, or there would be a significant overhead associated with dividing up uses of the shared resource in a way that permits more frequent yields.

In the end, it isn't clear that the overhead of locking is really worse.

debater (talk) 14:28, 9 September 2009 (UTC)

Real time
I think the current 'Real time' section is a little too brief and vague:

Another reason for multitasking was in the design of real-time computing systems, where there are a number of possibly unrelated external activities needed to be controlled by a single processor system. In such systems a hierarchical interrupt system was coupled with process prioritization to ensure that key activities were given a greater share of available process time.

I propose to rewrite it as follows:

The preemptive multitasking model provides a convenient programming model for dealing with high-speed I/O.

For a long time computers have used an interrupt handling model to enable the CPU to deal with high-speed I/O events efficiently. The CPU can be doing useful work without having to poll waiting. When an event occurs, the interrupt mechanism directs the CPU to execute a interrupt handler to deal with the event. When the interrupt handler has finished, normal execution can proceed from where it was interrupted.

However, the interrupt handler is itself limited. It must never take too long to complete, because all the time it is executing it cannot itself be interrupted. To prevent the possibility of two or more simultaneous (or nearly simultaneous) events being handled too slowly, interrupt handlers must finish very quickly.

The only solution to this limitation is to have high-speed I/O events dealt with in two stages. The first stage is carried out by the interrupt handler, which performs the very minimum actions necessary to deal with the event expediently. This includes sending some signal to the second stage.

The second stage of handling is carried out by normal (interruptible) piece of software, which generally does not have any of the limitations of an interrupt handler.

The preemptive multitasking model provides a ready-made programming model for this two-stage approach, because the second stage can be a thread which blocks on a signal (e.g. a lock) controlled by the first stage (the interrupt handler).

The mechanisms for prioritization of threads can be used to control the execution of the second stages. These mechanisms may be quite sophisticated, and may be chosen for suitability for real-time applications. This can be a factor which makes a preemptive multitasking model especially convenient for some real-time applications.

Note, however, that for many ‘hard’ real-time applications—where responsivity needs to be tightly confined and guaranteed—preemptive multitasking is not practicable. This is currently an an area of advanced research.

I've put it here for people to review first, rather than just shoving it in.

I'm currently looking to find some references. If anyone can suggest any, I'd be grateful.

Does this article explain what a thread is? It should do!

debater (talk) 14:15, 9 September 2009 (UTC)

Proposed merge of Multi-tasking with Multiprogramming
. Having established Multiprogramming as an independent topic from Multi-tasking one year ago, I would again oppose this suggestion.

From my practical experience in the field, the two concepts and definitions should not be confused; Neither is necessarily a subset of the other. (Multi-tasking came after multiprogramming, thus many systems which have multi-tasking do so to facilitate multiprogramming —but not necessarily all!). "Multiprogramming" currently has a section which draws distinctions between the two.

For that reason (to reduce redundancy), I might consider an argument to include a complete treatment of Multi-tasking under the heading of Multiprogramming, along with the various associated concepts: Cooperative vs. Preemptive vs. Time-slice Multi-tasking, Real time, Multi-threading, etc.

Many of these terms were coined by competing technology companies— IBM, Univac, Burroughs, General Electric, et al, and their definitions vary somewhat depending on whose manuals and textbooks one is reading.

They are all parallel but distinct and different technologies which were developed at different times and places by different parties to solve different problems.

If you want to lump them all together under one topic, I suggest "Computer System Resource Allocation" —and include other definitions such as dedicated resources, virtual systems, memory management, paging, multiprocessing, redundant arrays, multiplexing, spooling, background processing, etc.

Sources said (talk) 06:49, 15 August 2010 (UTC)

Was cooperative multitasking first?
The present article contains the sentence: Early multitasking systems used applications that voluntarily ceded time to one another. This is true for early home computers, but is it true for computers in general? This sentence was added to the article before its (recorded) history starts so it's a little difficult for me to track down what its author meant to say. Rp (talk) 14:19, 8 August 2011 (UTC)
 * In the beginning we inserted 'wait' instructions in the code - typically, but not limited to - every time a peripheral unit (card reader, printer, ...) was accessed in order to voluntarily give up the time slice. — Preceding unsigned comment added by John.St (talk • contribs) 10:32, 11 August 2011 (UTC)
 * "In the beginning" i.e. the 1960-70'es. John.St (talk) 17:49, 13 August 2011 (UTC)

Multitask ( Cooking)
Hi, I'm Ved Kumar What does Multitask mean? For example, ( My Mum is multitasking to cook for me) Does that make any scence? — Preceding unsigned comment added by 86.176.49.109 (talk) 17:33, 25 April 2013 (UTC)

Multitasking and multithreading
Just wanted to add some historical facts about the terminology in use today. In the mid 1960s, companies like Digital Equipment, Data General and Interdata (to name a few), started producing what was then called mini-computers. Many had somewhat primitive operating systems, with only two user processes running, which were called the "foreground" and the "background" processes. When an application initiated an I/O (i.e., disk read), the process would be blocked until the I/O would complete. To attain simultaneity, the operating systems supported an API which was called "multi-tasking". This API allowed programmers to write code that would run as separate tasks into one of the two processes, much as today's "threads". (They were light weight processes, with fast context switching, and they share memory and even code if so desired). With the advent of the IBM Personal Computer, which was started out with a single task operating system (DOS), the need to be able to perform more than one task at a time became obvious, and as it was implemented, the term "multi-tasking" was "usurped" from the mini-computer world by those that had never heard of it. When the Unix world became aware of the advantages of having light weight processes, the "wheel" was renamed (not re-invented), and we got what is today known as Posix threads (again, nothing new, a renaming of the concept used by mini-computers during the mid 1960s through mid 1970s). I personally worked with both the old mini-computer multitasking systems and Posix threads, so I am very familiar with them. — Preceding unsigned comment added by Bobcasas1 (talk • contribs) 17:26, 15 July 2013 (UTC)

Change the picture?
Wikipedia is not a soapbox — Preceding unsigned comment added by 70.59.27.125 (talk) 18:50, 29 October 2013 (UTC)
 * So what picture would you suggest in place of the one currently in the article? GB fan 18:56, 29 October 2013 (UTC)
 * I currently don't have a picture, but I'd be willing to find/make a new one. I just think the choice of programs/things running seems like they are trying to push some sort of viewpoint. If you're trying to have the same "purpose" without the possibly un-intentional propaganda, it'd just need to be a screen with multiple programs running. 70.59.27.125 (talk) 19:12, 29 October 2013 (UTC)
 * Now have a picture, replaced picture with a somewhat simular picture(but without political "taint". (Why this artical has such a political image for a un-political topic is a bit beyond me). Benjamintf1 (talk)

Memory protection
Are the 'citation needed' tags really required on the 'Memory protection' section? There must be a point where generic background knowledge makes explicit citations irrelevant.

For example "When multiple programs are present in memory, an ill-behaved program may (inadvertently or deliberately) overwrite memory belonging to another program, or even to the operating system itself". Does this really require a citation? Mtpaley (talk) 00:12, 13 November 2013 (UTC)

 * Proper references are required for any claim made in any Wikipedia article. This is not 'generic background knowledge' as you claim but a specific phenomenon (if indeed it exists).  The only time references are not required are for very obvious statements such as, "The sky is blue" (See WP:BLUE), but even then there must exist generic references that state that the sky is blue.  Though having said, I note that the Wikipedia article on Sky has no less than four references to support the claim that the sky is blue.  86.140.145.17 (talk) 08:58, 10 March 2014 (UTC)

Factual problems...
Many of the claims in this article are incorrect. Here is but one example:

"Despite the difficulty of designing and implementing cooperatively multitasked systems, time-constrained, real-time embedded systems (such as spacecraft) are often implemented using this paradigm. This allows highly reliable, deterministic control of complex real time sequences, for instance, the firing of thrusters for deep space course corrections."

This is not true. The entire reason servers and all modern operating systems, desktop, and embedded are exclusively preemptive is because cooperative multitasking was inherently *unreliable*. The only reason to use cooperative multitasking is ease of implementation, as it required no special hardware and only a very simple scheduler.

Today, almost all spacecraft use preemptive multitasking - along with almost everything else. Almost every operating system, all modern versions of Windows, linux variants, BSD variants, Mac, Android all use preemptive multitasking including VxWorks - the OS that runs spacecraft including the Curiosity rover, Deep Impact, James Webb Space Telescope, Mars Pathfinder, Spirit and Opportunity, SpaceX Dragon, Deep Impact, Phoenix Mars Lander... and so on. The ISS runs Debian, itself a preemptive multitasking OS. Safety critical systems such as avionics run hardware level preemptive schedulers to guarantee CPU time, such as the case with the F-35 avionics running Green Hills software's Integrity OS - specifically chosen because of it's rigorous preemptive multitasking and memory protections.

I can find no reference to any spacecraft built in the last 30 years that relies on cooperative multitasking and for obvious reason; A single erroneous subroutine could hang the entire system or put lives in jeopardy.

Vcfahrenbruck (talk) 12:23, 14 March 2014 (UTC)

 * Hello there! Just as a note, you're more than welcome to edit and improve this article.  Just provide a few references, and off you go. :) — Dsimic (talk | contribs) 22:08, 15 March 2014 (UTC)

 * If something lacks references feel free to add a box above it, write [Citation Needed], remove it, or improve it (as long as it follows WP:SYNTH), so go ahead.
 * Sincerely, --Namlong618 (talk) 08:12, 27 February 2015 (UTC)

External links modified
Hello fellow Wikipedians,

I have just added archive links to 1 one external link on Computer multitasking. Please take a moment to review my edit. If necessary, add after the link to keep me from modifying it. Alternatively, you can add to keep me off the page altogether. I made the following changes:
 * Added archive https://web.archive.org/20120214162409/http://www.smartcomputing.com/editorial/article.asp?article=articles%2F2005%2Fs1606%2F08s06%2F08s06.asp to http://www.smartcomputing.com/editorial/article.asp?article=articles%2F2005%2Fs1606%2F08s06%2F08s06.asp

When you have finished reviewing my changes, please set the checked parameter below to true to let others know.

Cheers. —cyberbot II  Talk to my owner :Online 21:05, 25 August 2015 (UTC)

 * Looking good. It's a reference, though. — Dsimic (talk | contribs) 05:30, 26 August 2015 (UTC)

Leo III not first
The section "multiprogramming" says that LEO III was the first to do multiprogramming. This is clearly not correct, since LEO III shipped in 1961 according to its article, and the Electrologica EL-X1 demonstrated multiprogramming in 1958. See "The X1 computer" by B.J. Loopstra, The Computer Journal (1959) 2 (1): 39-43 Paul Koning (talk) 16:14, 4 November 2015 (UTC)

 * This statement is entirely false indeed, we're publishing inaccurate information. I'll revise the paragraph to include details about the Bull Gamma 60 and X1 computers while removing the claim that the Leo III was the first. Damien.b (talk) 12:12, 10 January 2024 (UTC)

GPUs
With the advent of GPUs, complex video data could be displayed rapidly provided that's the only task assigned to it. In recent years, the use of GPUs as a powerful math coprocessor has become common through the use of languages sucn as OpenCL or CUDA. The big shortcoming in that concept is that GPUs lack a functional operating system and are therefore not amenable to effective multitasking. A topic on "Stream Computing" should mention these facts, together with a clear statement of what needs to happen in the future. — Preceding unsigned comment added by 208.127.217.116 (talk) 23:06, 6 April 2017 (UTC)

Main image doesn't represent multitasking very well
It's like someone asking what a symphony sounds and you listing off all the instruments, giving a brief mechanical description of each and neglecting to mention the composer, the conductor, the time signature, and how the instruments take on different roles, compliment each other, harmonize, etc.

There are baked user interfaces of a variety of programs looking pretty and not doing much else. You couldn't even comfortably human multitask https://en.m.wikipedia.org/wiki/Human_multitasking the way in which the windows are configured — Preceding unsigned comment added by 2601:643:103:F170:ECDC:349F:26BD:4841 (talk) 21:11, 19 August 2017 (UTC)

Dear poor author
Ever hear of citations? — Preceding unsigned comment added by 2601:46:200:5671:5C61:5225:2DC5:A22 (talk) 07:45, 28 July 2018 (UTC)

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

title: Talk:Computer multitasking


text:
Compression ratio

The compression ratio is the ratio between the volume of the cylinder and combustion chamber in an internal combustion engine at their maximum and minimum values.

A fundamental specification for such engines, it is measured two ways: the static compression ratio, calculated based on the volume of the cylinder when the piston is at the bottom of its stroke, and the volume of the cylinder when the piston is at the top of its stroke.

The dynamic compression ratio is a more advanced calculation which also takes into account gases entering and exiting the cylinder during the compression phase.

Effect and typical ratios
A high compression ratio is desirable because it allows an engine to extract more mechanical energy from a given mass of air–fuel mixture due to its higher thermal efficiency. This occurs because internal combustion engines are heat engines, and higher compression ratios permit the same combustion temperature to be reached with less fuel, while giving a longer expansion cycle, creating more mechanical power output and lowering the exhaust temperature.

Petrol engines
In petrol (gasoline) engines used in passenger cars for the past 20 years, compression ratios have typically been between 8:1 and 12:1. Several production engines have used higher compression ratios, including:
 * Cars built from 1955–1972 which were designed for high-octane leaded gasoline, which allowed compression ratios up to 13:1.
 * Some Mazda SkyActiv engines released since 2012 have compression ratios up to 16:1.  The SkyActiv engine achieves this compression ratio with ordinary unleaded gasoline (95 RON in the United Kingdom) through improved scavenging of exhaust gases (which ensures cylinder temperature is as low as possible before the intake stroke), in addition to direct injection.
 * Toyota Dynamic Force engine has a compression ratio up to 14:1.
 * The 2014 Ferrari 458 Speciale also has a compression ratio of 14:1.

When forced induction (e.g. a turbocharger or supercharger) is used, the compression ratio is often lower than naturally aspirated engines. This is due to the turbocharger or supercharger already having compressed the air before it enters the cylinders. Engines using port fuel-injection typically run lower boost pressures and/or compression ratios than direct injected engines because port fuel injection causes the air–fuel mixture to be heated together, leading to detonation. Conversely, directly injected engines can run higher boost because heated air will not detonate without a fuel being present.

Higher compression ratios can make gasoline (petrol) engines subject to engine knocking (also known as "detonation", "pre-ignition", or "pinging") if lower octane-rated fuel is used. This can reduce efficiency or damage the engine if knock sensors are not present to modify the ignition timing.

Diesel engines
Diesel engines use higher compression ratios than petrol engines, because the lack of a spark plug means that the compression ratio must increase the temperature of the air in the cylinder sufficiently to ignite the diesel using compression ignition. Compression ratios are often between 14:1 and 23:1 for direct injection diesel engines, and between 18:1 and 23:1 for indirect injection diesel engines.

At the lower end of 14:1, NOx emissions are reduced at a cost of more difficult cold-start. Mazda's Skyactiv-D, the first such commercial engine from 2013, used adaptive fuel injectors among other techniques to ease cold start.

Other fuels
The compression ratio may be higher in engines running exclusively on liquefied petroleum gas (LPG or "propane autogas") or compressed natural gas, due to the higher octane rating of these fuels.

Kerosene engines typically use a compression ratio of 6.5 or lower. The petrol-paraffin engine version of the Ferguson TE20 tractor had a compression ratio of 4.5:1 for operation on tractor vaporising oil with an octane rating between 55 and 70.

Motorsport engines
Motorsport engines often run on high-octane petrol and can therefore use higher compression ratios. For example, motorcycle racing engines can use compression ratios as high as 14.7:1, and it is common to find motorcycles with compression ratios above 12.0:1 designed for 95 or higher octane fuel.

Ethanol and methanol can take significantly higher compression ratios than gasoline. Racing engines burning methanol and ethanol fuel often have a compression ratio of 14:1 to 16:1.

Mathematical formula
In a piston engine, the static compression ratio ($$\mathrm{CR}$$) is the ratio between the volume of the cylinder and combustion chamber when the piston is at the bottom of its stroke, and the volume of the combustion chamber when the piston is at the top of its stroke. It is therefore calculated by the formula $$\mathrm{CR} = \frac { V_d + V_c} {V_c}$$

where
 * $$V_d$$ is the displacement volume. This is the volume inside the cylinder displaced by the piston from the beginning of the compression stroke to the end of the stroke.
 * $$V_c$$ is the clearance volume. This is the volume of the space in the cylinder left at the end of the compression stroke.

$$V_d$$ can be estimated by the cylinder volume formula: $$V_d = \tfrac{\pi} {4} b^2 s$$

where
 * $$b$$ is the cylinder bore (diameter)
 * $$s$$ is the piston stroke length

Because of the complex shape of $$V_c$$ it is usually measured directly. This is often done by filling the cylinder with liquid and then measuring the volume of the used liquid.

Variable compression ratio engines
Most engines use a fixed compression ratio, however a variable compression ratio engine is able to adjust the compression ratio while the engine is in operation. The first production engine with a variable compression ratio was introduced in 2019.

Variable compression ratio is a technology to adjust the compression ratio of an internal combustion engine while the engine is in operation. This is done to increase fuel efficiency while under varying loads. Variable compression engines allow the volume above the piston at top dead centre to be changed.

Higher loads require lower ratios to increase power, while lower loads need higher ratios to increase efficiency, i.e. to lower fuel consumption. For automotive use this needs to be done as the engine is running in response to the load and driving demands.

The 2019 Infiniti QX50 is the first commercially available car that uses a variable compression ratio engine.

Dynamic compression ratio
The static compression ratio discussed above — calculated solely based on the cylinder and combustion chamber volumes — does not take into account any gases entering or exiting the cylinder during the compression phase. In most automotive engines, the intake valve closure (which seals the cylinder) takes place during the compression phase (i.e. after bottom dead centre, BDC), which can cause some of the gases to be pushed back out through the intake valve. On the other hand, intake port tuning and scavenging can cause a greater amount of gas to be trapped in the cylinder than the static volume would suggest. The dynamic compression ratio accounts for these factors.

The dynamic compression ratio is higher with more conservative intake camshaft timing (i.e. soon after BDC), and lower with more radical intake camshaft timing (i.e. later after BDC). Regardless, the dynamic compression ratio is always lower than the static compression ratio.

Absolute cylinder pressure is used to calculate the dynamic compression ratio, using the following formula: $$P_\text{cylinder} = P_\text{atmospheric} \times \text{CR}^\gamma$$ where $$\gamma$$ is a polytropic value for the ratio of specific heats for the combustion gases at the temperatures present (this compensates for the temperature rise caused by compression, as well as heat lost to the cylinder)

Under ideal (adiabatic) conditions, the ratio of specific heats would be 1.4, but a lower value, generally between 1.2 and 1.3 is used, since the amount of heat lost will vary among engines based on design, size and materials used. For example, if the static compression ratio is 10:1, and the dynamic compression ratio is 7.5:1, a useful value for cylinder pressure would be 7.51.3 × atmospheric pressure, or 13.7 bar (relative to atmospheric pressure).

The two corrections for dynamic compression ratio affect cylinder pressure in opposite directions, but not in equal strength. An engine with high static compression ratio and late intake valve closure will have a dynamic compression ratio similar to an engine with lower compression but earlier intake valve closure.

title: Compression ratio


text:
Concordat of Worms

The Concordat of Worms (Concordatum Wormatiense; Wormser Konkordat), also referred to as the Pactum Callixtinum or Pactum Calixtinum, was an agreement between the Catholic Church and the Holy Roman Empire which regulated the procedure for the appointment of bishops and abbots in the Empire. Signed on 23 September 1122 in the German city of Worms by Pope Callixtus II and Emperor Henry V, the agreement set an end to the Investiture Controversy, a conflict between state and church over the right to appoint religious office holders that had begun in the middle of the 11th century.

By signing the concordat, Henry renounced his right to invest bishops and abbots with ring and crosier, and opened ecclesiastical appointments in his realm to canonical elections. Callixtus, in turn, agreed to the presence of the emperor or his officials at the elections and granted the emperor the right to intervene in the case of disputed outcomes. The emperor was also allowed to perform a separate ceremony in which he would invest bishops and abbots with a sceptre, representing the imperial lands associated with their episcopal see.

Background
During the middle of the 11th century, a reformist movement within the Christian Church sought to reassert the rights of the Holy See at the expense of the European monarchs. Having been elected in 1073, the reformist Pope Gregory VII proclaimed several edicts aimed at strengthening the authority of the papacy, some of which were formulated in the Dictatus papae of 1075. Gregory's edicts postulated that secular rulers were answerable to the pope and forbade them to make appointments to clerical offices (a process known as investiture).

The pope's doctrines were vehemently rejected by Henry IV, the Holy Roman Emperor, who habitually invested the bishops and abbots of his realm. The ensuing conflict between the Empire and the papacy is known as the Investiture Controversy. The dispute continued after the death of Gregory VII in 1084 and the abdication of Henry IV in 1105.

Even though Henry's son and successor, Henry V, looked towards reconciliation with the reformist movement, no lasting compromise was achieved in the first 16 years of his reign. In 1111, Henry V brokered an agreement with Pope Paschal II at Sutri, whereby he would abstain from investing clergy in his realm in exchange for the restoration of church property that had originally belonged to the Empire. The Sutri agreement, Henry hoped, would convince Paschal to assent to Henry's official coronation as emperor.

The agreement failed to be implemented, leading Henry to imprison the pope. After two months of captivity, Paschal vowed to grant the coronation and to accept the emperor's role in investiture ceremonies. He also agreed never to excommunicate Henry. Given that these concessions had been won by force, ecclesiastical opposition to the Empire continued. The following year, Paschal reneged on his promises.

Mouzon summit
In January 1118, Pope Paschal died. He was succeeded by Gelasius II, who died in January 1119. His successor, the Burgundian Callixtus II, resumed negotiations with the Emperor with the aim of settling the dispute between the church and the Empire. In the autumn of 1119, two papal emissaries, William of Champeaux and Pons of Cluny, met Henry at Strasbourg, where the emperor agreed in principle to abandon the secular investiture ceremony that involved giving new bishops and abbots a ring and a crosier.

The two parties scheduled a final summit between Henry and Callixtus at Mouzon, but the meeting ended abruptly after the emperor refused to accept a short-notice change in Callixtus's demands. The church leaders, who were deliberating their position at a council in Reims, reacted by excommunicating Henry. However, they did not endorse the pope's insistence upon the complete abandonment of secular investiture. The negotiations ended in failure.

Historians disagree as to whether Calixtus actually wanted peace or fundamentally mistrusted Henry. Due to his uncompromising position in 1111, Calixtus has been termed an "ultra", and his election to the papacy may indicate that the College of Cardinals saw no reason to show weakness to the emperor. This optimism about victory was founded on the very visible, and very vocal opposition to Henry from within his own nobility, and the cardinals may have seen the emperor's internal weaknesses as an opportunity for outright victory.

Further negotiations
After the failure of the Mouzon negotiations, and the disappearance into the horizon of the chances of Henry's unconditional surrender, the majority of the clergy became willing to compromise in order to settle the dispute. The polemic writings and pronouncements that had figured so highly during the Investiture Dispute had died down by this point. Historian Gerd Tellenbach argues that, despite appearances, these years were "no longer marked by an atmosphere of bitter conflict".

This was in part the result of the papacy's realization that it could not win two different disputes on two separate fronts, as it had been trying to do. Calixtus had been personally involved in negotiations with the Emperor over the last decade, and his intimate knowledge of the delicate situation made him the perfect candidate for the attempt. The difference between 1119 and 1122, argues Stroll, was not Henry, who had been willing to make concessions in 1119, but Calixtus, who had then been intransigent, but who now was intent upon reaching an agreement".

The same sentiment prevailed in much of the German nobility. In 1121, pressured by a faction of nobles from the Lower Rhine and Duchy of Saxony under the leadership of the archbishop Adalbert of Mainz, Henry agreed to submit to make peace with the pope. In response in February 1122, Calixtus wrote to Frederick in a conciliatory tone via the Bishop of Acqui. His letter has been described as "a carefully crafted overture".

Calixtus drew attention to their blood relationship, suggesting that while their shared ancestry compelled them to love each other as brothers, it was fundamental that the German kings draw their authority from God, but via his servants, not directly. However, Calixtus also emphasised for the first time that he blamed not Henry personally for the dispute but his bad advisors who had dictated unsound policy to him. In a major shift in policy since the Council of Reims of 1119, the pope stated that the church gifts what it possesses to all its children, without making claims upon them. This was intended to reassure Henry that in the event of peace between them, his position and Empire were secure.

Shifting from the practical to the spiritual, Calixtus asked Henry to bear in mind that he was a king, but like all men limited on his earthly capability; he had armies, and kings below him, but the church had Christ and the Apostles. Continuing his theme, he referred, indirectly, to Henry's excommunication by himself (twice), he begged Henry to allow the conditions for peace to be created, as a result of which the church's, and God's glory would be increased, as concomitantly would the Emperor's. Conversely, he made sure to include a threat: if Henry did not change his ways, Calixtus threatened to place "the protection of the church in the hands of wise men".

Historian Mary Stroll argues that, in taking this approach, Calixtus was taking advantage of the fact that, while he himself "was hardly in a position to sabre rattle" due to his military defeat in the south and his difficulty with his own Cardinals, Henry was also under pressure in Germany in both the military and spiritual spheres.

The Emperor replied through the Bishop of Speyer and the Abbot of Fulda, who travelled to Rome and collected the pope's emissaries under the Cardinal Bishop of Ostia. Speyer was a representative of Henry's political opponents in Germany, whereas Fulda was a negotiator rather than politically partisan. Complicating matters was a disputed election to the bishopric of Wurzburg in February 1122 of the kind that was at the heart of the Investiture Dispute. Although this almost led to an outbreak of civil war, a truce was arranged in August, allowing the parties to return to the papal negotiations.

In the summer of 1122, a synod was convened in Mainz, at which imperial emissaries concluded the terms of their agreement with representatives of the church. In a sign that the Pope intended the impending negotiations to be successful, a Lateran council was announced for the following year.

Worms
The Emperor received the papal legates in Worms with due ceremony, where he awaited the outcome of the negotiations which appear to have actually taken place in nearby Mainz, which was hostile territory to Henry. As such, he had to communicate via messenger to keep up with events. Abbot Ekkehard of Aura chronicles that discussions took over a week to conclude. On 8 September, he met the papal legates and their final agreements were codified for publication.

Although a possible compromise solution had already been received from England, this does not seem to have ever been considered in depth, probably on account of it containing an oath of Homage between Emperor and Pope, which been a historical sticking point in earlier negotiations. The papal delegation was led by Cardinal bishop Lamberto Scannabecchi of Ostia, the future Pope Honorius II.

Both sides studied previous negotiations between them, including those from 1111, which were considered to have created precedent. On 23 September 1122, papal and imperial delegates signed a series of documents outside the walls of Worms. There was insufficient room in the city for the number of attendees and watchers. Adalbert, Archbishop of Mainz wrote to Calixtus of how complex the negotiations had been, given that, as he said, Henry regarded the powers he was being asked to renounce as being hereditary in the Imperial throne. It is probable that what was eventually promulgated was the result of almost every word being carefully considered. The main difference between what was to be agreed at Worms and previous negotiations were the concessions from the pope.

Concordat
The agreements come to at Worms were in the nature of both concessions and assurances to the other party. Henry, on oath before God, the apostles and the church renounced his right to invest bishops and abbots with ring and crosier, and opened ecclesiastical appointments in his realm to canonical elections, regno vel imperio. He also recognised the traditional extent and boundaries of the papal patrimony as a legal entity rather than one malleable to the emperor. Henry promised to return to the church those lands rightfully belonging to the church seized by himself or his father to the church; furthermore, he would assist the pope in regaining those that were taken by others, and "he will do the same thing for all other churches and princes, both ecclesiastical and lay". If the pope requested Imperial assistance, he would receive it, and if the church came to the empire for justice, it would be treated fairly. He also swore to abstain from "all investiture by ring and staff", marking the end of an ancient imperial tradition.

Callixtus made similar reciprocal promises regarding the empire in Italy. He agreed to the presence of the emperor or his officials at the elections and granted the emperor the right to ajudge in the case of disputed outcomes on episcopal advice—as long as they had been held peacefully and without simony—which had officially been the case ever since precedent had been set by the London Accord of 1107. This right to judge was constrained by an assurance that he would support the majority vote among electors, and further that he would take the advice of his other bishops before doing so. The emperor was also allowed to perform a separate ceremony in which he would invest bishops and abbots with their regalia, a sceptre representing the imperial lands associated with their episcopal see. This clause also contained a "cryptic" condition that once the elect had been so endowed, the new bishop "should do what he ought to do according to imperial rights". In the German imperial lands this was to take place prior to the bishop-elect's consecration; elsewhere in the empire—Burgundy and Italy, exempting the Papal States—within six months of the ceremony. The differentiating between the German portion of the Empire and the rest was of particular importance to Calixtus as the papacy had traditionally felt threatened more from it in the peninsular than the broader Empire. Finally, the pope granted "true peace" on the emperor and all those who had supported him. Calixtus had effectively overturned wholesale the strategy he had pursued during the Mouzon negotiation; episcopal investitures in Germany were to take place with very little substantive change in ceremony, while temporal involvement remained, only replacing investiture with homage, although the word itself—hominium—was studiously avoided. Adalbert, from whom Calixtus first received news of the final concordat, emphasized that it still had to be approved in Rome; this suggests, argues Stroll, that the Archbishop—and probably the papal legation as a whole—were against making concessions to the emperor, and probably wanted Calixtus to disown the agreement. Adalbert believed the agreement would make it easier for the Emperor to legalise intimidation of episcopal electors, writing that "through the opportunity of [the emperor's] presence, the Church of God must undergo the same slavery as before, or an even more oppressive one".

However, argues Stroll, the concessions Calixtus made were an "excellent bargain" in return for eradicating the danger on the papacy's northern border and therefore allowing him to focus, without threat or distraction, on the Normans to the south. It had achieved its peace, argues Norman Cantor, by allowing local national custom and practice to determine future relations between crown and pope; in most cases, he notes, this "favored the continuance of royal control over the church".

The concordat was published as two distinct charters, each laying out the concessions the one party was making to the other. They are known respectively as the Papal (or the Calixtinum) and the Imperial (Henricianum) charters. Calixtus's is addressed to the emperor—in quite personal terms—while Henry's is made out to God. The bishop of Ostia gave the emperor the kiss of peace on behalf of the pope and said Mass. By these rites was Henry returned to the church, the negotiators were lauded for succeeding in their delicate mission and the concordat was called "peace at the will of the pope". Neither charter was signed; both contained probably intentional vagaries and unanswered questions—such as the position of the papacy's churches that lay outside both the patrimony and Germany—which were subsequently addressed on a case-by-case basis. Indeed, Robert Benson has suggested that the brevity of the charters was deliberate and that the agreement as a whole is as important for what it omits as for what it includes. The term regalia, for example, was not only undefined but literally meant two different things to each party. In the Henricianum it referred to the feudal duty owed to a monarch; in the Calixtinium, it was the episcopal temporalities. Broader question, such as the nature of the church and Empire relationship, were also not addressed, although some ambiguity was removed by an 1133 Papal privilege.

The Concordat was widely, and deliberately, publicised around Europe. Calixtus was not in Rome when the concordat was delivered. He had left the city by late August and was not to return until mid- to late October, making a progress to Anagni, taking the bishopric of Anagni and Casamari Abbey under his protection.

Preservation
The concordat was ratified at the First Council of the Lateran and the original Henricianum charter is preserved at the Vatican Apostolic Archive; the Calixtinum has not survived except in subsequent copies. A copy of the former is also held in the Codex Udalrici, but this is an abridged version for political circulation, as it reduces the number of imperial concessions made. Indicating the extent that he saw the agreement as a papal victory, Calixtus had a copy of the Henricianum painted on a Lateran Palace chamber wall; while nominally portraying the concordat as a victory for the papacy, it also ignored the numerous concessions made to the emperor. This was part of what Hartmut Hoffmann has called "a conspiracy of silence" regarding papal concessions. Indeed, while the Pope is pictured enthroned, and Henry only standing, the suggestion is still that they were jointly wielding their respective authority to come to this agreement. An English copy of the Calixtinum made by William of Malmsbury is reasonably accurate but omits the clause mentioning the use of a sceptre in the granting of the regalia. He then, having condemned Henry's "Teuton fury", proceeds to praise him, comparing him favourably to Charlemagne for his devotion to God and the peace of Christendom.

Aftermath
The first invocation of the concordat was not in the empire, as it turned out, but by Henry I of England the following year. Following a long-running dispute between Canterbury–York which ended up in the Papal court, Joseph Huffman argues that it would have been controversial for the Pope "to justify one set of concessions in Germany and another in England". The concordat ended once and for all the "Imperial church system of the Ottonians and Salians". The First Lateran Council was convoked to confirm the Concordat of Worms. The council was most representative with nearly 300 bishops and 600 abbots from every part of Catholic Europe being present. It convened on March 18, 1123. One of its primary concerns was to emphasise the independence of diocesan clergy, and to do so it forbade monks to leave their monasteries to provide pastoral care, which would in future be the sole preserve of the diocese. In ratifying the Concordat, the Council confirmed that in future bishops would be elected by their clergy, although, also per the Concordat, the Emperor could refuse the homage of German bishops.

Decrees were passed directed against simony, concubinage among the clergy, church robbers, and forgers of Church documents; the council also reaffirmed indulgences for Crusaders. These, argues C. Colt Anderson "established important precedents in canon law restricting the influence of the laity and the monks". While this led to a busy period of reform, it was important for those advocating reform not to allow themselves to be confused with the myriad heretical sects and schismatics who were making similar criticisms.

The Concordat was the last major achievement for Emperor Henry, as he died in 1125; an attempted invasion of France came to nothing in 1124 in the face of "determined opposition". Fuhrmann comments that, as Henry had shown in his life "even less interest in new currents of thought and feeling than his father", he probably did not understand the significance of the events he had lived through. The peace only lasted until his death; when Imperial Electors met to choose his successor, reformists took the opportunity to attack the imperial gains of Worms on the grounds that they had been granted to him personally rather than Emperors generally. However, later emperors, such as Frederick I and Henry VI, continued to wield as much, if intangible, power as their predecessors in episcopal elections, and to a greater degree to that allowed them by Calixtus' charter. Successive emperors found the Concordat sufficiently favourable that it remained, almost unaltered until the empire was dissolved by Francis II in 1806 on account of Napoleon. Popes, likewise, were able to use the powers codified to them in the Concordatto their advantage in future internal disputes with their Cardinals.

Reception
The most detailed contemporary description of the Concordat comes to historians through a brief chronicle known as the 1125 continuation chronicle. This pro-papal document lays the blame for the schism squarely upon Henry—by his recognition of Gregory VIII—and the praise for ending it on Calixtus, through his making only temporary compromises. I. S. Robinson, writing in The New Cambridge Medieval History, suggests that this was a deliberate ploy to leave further negotiations open with a more politically malleable Emperor in future. To others it was not so clear cut; Honorius of Autun, for example, writing later in the century discussed lay investiture as an aspect of papal-Imperial relations and, even a century later the Sachsenspiegel still stated that Emperors nominated bishops in Germany. Robinson suggests that, by the end of the 12th century, "it was the imperial, rather than the papal version of the Concordat of Worms that was generally accepted by German churchmen".

The contemporary English historian William of Malmesbury praised the Concordat for curtailing what he perceived as the emperor's overreach, or as he put it, "severing the sprouting necks of Teuton fury with the axe of Apostolic power". However, he regarded the final settlement not as a defeat of the Empire at the hands of the church, but rather as a reconciliatory effort by the two powers. Although polemicism had died down in the years preceding the Concordat, it did not finish them completely, and factionalism within the church especially continued. Gerhoh of Reichersberg believed that the emperor now had the right to request German bishops pay homage to him, something that would never have been allowed under Paschal, due to the vague clause instructing newly-elects to the things the emperor wished. Gerhoh argued that now imperial intervention in episcopal elections had been curtailed, Henry would use this clause to extend his influence in the church by means of homage. Gerhoh was torn between viewing the concordat as the end of a long struggle between pope and empire, or whether it marked the beginning of a new one within the church itself. Likewise Adelbert of Mainz—who had casually criticised the agreement in his report to Calixtus continued to lobby against it, and continued to bring complaints against Henry, whom, for example, he alleged had illegally removed the Bishop of Strassburg who was suspected of complicity in the death of Duke Berthold of Zaehringen.

The reformist party within the church took a similar view, criticising the Concordat for failing to remove all secular influence on the church. For this reason, a group of followers of Paschal II unsuccessfully attempted to prevent the agreement's ratification at the Lateran Council, crying non placet! when asked to do so: "it was only when it was pointed out that much had to be accepted for the sake of peace that the atmosphere quietened". Calixtus told them that they had "not to approve but tolerate" it. At a council in Bamberg in 1122 Henry gathered those nobles who had not attended the Concordat to seek their approval of the agreement, which they did. The following month he sent cordial letters to Calixtus agreeing with the pope's position that as brothers in Christ they were bound by God to work together, etc., and that he would soon visit personally to discuss the repatriation of papal land. These letters were, in turn, responded to positively by Calixtus, who instructed his delegates to make good the promises they had made at Worms.

Historiography
Gottfried Wilhelm Leibniz called the agreements made at Worms "the oldest concordat in German history, an international treaty", while Augustin Fliche argued that the Concordat effectively instituted the statutes of Ivo of Chartres, a prominent reformer in the early years of the Investiture Contest, a view, it has been suggested, that most historians agree with. The historian Uta-Renate Blumenthal writes that, despite its shortcomings, the Concordat freed "[the church and the Empire] from antiquated concepts with their increasingly anachronistic restrictions". According to the historian William Chester Jordan, the Concordat was "of enormous significance" because it demonstrated that the emperor, in spite of his great secular power, did not have any religious authority. On the other hand, argues Karl F. Morrison, any victory the papacy felt it had won was pyrrhic, as "the king was left in possession of the field". The new peace also now allowed the papacy to expand its territories in Italy, such as the Sabina, which were unobtainable while the dispute with Henry was ongoing, while in Germany, a new class of ecclesiastics was created, what Horst Fuhrmann calls the "ecclesiastical princes of the Empire".

While most historians agree that the Concordat marks a clear close to the fifty-year-old struggle between church and empire, disagreement continues on just how decisive a termination that was. Historians are also unclear as to the commitment of the pope to the concordat. Stroll, for example, notes that, while Henry's oaths were made to the church corporate, so in perpetuity, while Calixtus's may have been in a personal capacity. This, Stroll argues, would mean that it could be argued that while Henry's commitments to the church applied forever, Calixtus's applied only for the duration of Henry's reign, and at least one contemporary, Otto of Freising, wrote later in the century that he believed this to be the church's position. Stroll considers it "implausible" that Henry and his counsel would ever have entered into such a one-sided agreement. Indeed, John O'Malley has argued that the emperor had effectively been granted a veto from Calixtus; while in the strictest interpretation of the Gregorian reformers the only two important things in the making of a bishop were his election and consecration, Calixtus had effectively codified a role—however small—for the emperor in this process. Conversely, Benson reckons that while Henry's agreement was with the church in perpetuity, Calixtus'—based on the personal mode of address—was with him personally, and as such not binding on his successors. However, this was also an acknowledgement, he suggests, that much of what the pope did not address was already considered customary, and so did not need addressing.

There has also been disagreement in why the Investiture contest ended with the Concordat as it did. Benson notes that, as a truce, it was primarily intended to stop the fighting rather than to address its original causes. It was "a straightforward, political engagement...a pragmatic agreement" between two political bodies. Indeed, controversy over investiture continued for at least another decade; in that light, suggests Benson, it could be argued that the Concordat did not end the dispute at all. There were "many problems unsolved, and [it] left much room for the free play of power". Political scientist Bruce Bueno de Mesquita has argued that, in the long term, the Concordat was an essential component to the later—gradual—creation of the European nation state.

title: Concordat of Worms


text: Talk:Concordat of Worms

title: Talk:Concordat of Worms


text:
Context-free language

In formal language theory, a context-free language (CFL), also called a Chomsky type-2 language, is a language generated by a context-free grammar (CFG).

Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by context-free grammars.

Context-free grammar
Different context-free grammars can generate the same context-free language. Intrinsic properties of the language can be distinguished from extrinsic properties of a particular grammar by comparing multiple grammars that describe the language.

Automata
The set of all context-free languages is identical to the set of languages accepted by pushdown automata, which makes these languages amenable to parsing. Further, for a given CFG, there is a direct way to produce a pushdown automaton for the grammar (and thereby the corresponding language), though going the other way (producing a grammar given an automaton) is not as direct.

Examples
An example context-free language is $$L = \{a^nb^n:n\geq1\}$$, the language of all non-empty even-length strings, the entire first halves of which are $a$'s, and the entire second halves of which are $b$'s. $L$ is generated by the grammar $$S\to aSb ~|~ ab$$. This language is not regular. It is accepted by the pushdown automaton $$M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, z, \{q_f\})$$ where $$\delta$$ is defined as follows:

 * $$\begin{align}

\delta(q_0, a, z) &= (q_0, az) \\ \delta(q_0, a, a) &= (q_0, aa) \\ \delta(q_0, b, a) &= (q_1, \varepsilon) \\ \delta(q_1, b, a) &= (q_1, \varepsilon) \\ \delta(q_1, \varepsilon, z) &= (q_f, \varepsilon) \end{align}$$

Unambiguous CFLs are a proper subset of all CFLs: there are inherently ambiguous CFLs. An example of an inherently ambiguous CFL is the union of $$\{a^n b^m c^m d^n | n, m > 0\}$$ with $$\{a^n b^n c^m d^m | n, m > 0\}$$. This set is context-free, since the union of two context-free languages is always context-free. But there is no way to unambiguously parse strings in the (non-context-free) subset $$\{a^n b^n c^n d^n | n > 0\}$$ which is the intersection of these two languages.

Dyck language
The language of all properly matched parentheses is generated by the grammar $$S\to SS ~|~ (S) ~|~ \varepsilon$$.

Context-free parsing
The context-free nature of the language makes it simple to parse with a pushdown automaton.

Determining an instance of the membership problem; i.e. given a string $$w$$, determine whether $$w \in L(G)$$ where $$L$$ is the language generated by a given grammar $$G$$; is also known as recognition. Context-free recognition 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.3728596). 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.

Practical uses of context-free languages require also to produce a derivation tree that exhibits the structure that the grammar associates with the given string. The process of producing this tree is called parsing. Known parsers have a time complexity that is cubic in the size of the string that is parsed.

Formally, the set of all context-free languages is identical to the set of languages accepted by pushdown automata (PDA). Parser algorithms for context-free languages include the CYK algorithm and Earley's Algorithm.

A special subclass of context-free languages are the deterministic context-free languages which are defined as the set of languages accepted by a deterministic pushdown automaton and can be parsed by a LR(k) parser.

See also parsing expression grammar as an alternative approach to grammar and parser.

Closure properties
The class of context-free languages is closed under the following operations. That is, if L and P are context-free languages, the following languages are context-free as well:
 * the union $$L \cup P$$ of L and P
 * the reversal of L
 * the concatenation $$L \cdot P$$ of L and P
 * the Kleene star $$L^*$$ of L
 * the image $$\varphi(L)$$ of L under a homomorphism $$\varphi$$
 * the image $$\varphi^{-1}(L)$$ of L under an inverse homomorphism $$\varphi^{-1}$$
 * the circular shift of L (the language $$\{vu : uv \in L \}$$)
 * the prefix closure of L (the set of all prefixes of strings from L)
 * the quotient L/R of L by a regular language R

Nonclosure under intersection, complement, and difference
The context-free languages are not closed under intersection. This can be seen by taking the languages $$A = \{a^n b^n c^m \mid m, n \geq 0 \}$$ and $$B = \{a^m b^n c^n \mid m,n \geq 0\}$$, which are both context-free. Their intersection is $$A \cap B = \{ a^n b^n c^n \mid n \geq 0\}$$, which can be shown to be non-context-free by the pumping lemma for context-free languages. As a consequence, context-free languages cannot be closed under complementation, as for any languages A and B, their intersection can be expressed by union and complement: $$A \cap B = \overline{\overline{A} \cup \overline{B}} $$. In particular, context-free language cannot be closed under difference, since complement can be expressed by difference: $$\overline{L} = \Sigma^* \setminus L$$.

However, if L is a context-free language and D is a regular language then both their intersection $$L\cap D$$ and their difference $$L\setminus D$$ are context-free languages.

Decidability
In formal language theory, questions about regular languages are usually decidable, but ones about context-free languages are often not. It is decidable whether such a language is finite, but not whether it contains every possible string, is regular, is unambiguous, or is equivalent to a language with a different grammar.

The following problems are undecidable for arbitrarily given context-free grammars A and B:
 * Equivalence: is $$L(A)=L(B)$$?
 * Disjointness: is $$L(A) \cap L(B) = \emptyset $$ ? However, the intersection of a context-free language and a regular language is context-free, hence the variant of the problem where B is a regular grammar is decidable (see "Emptiness" below).
 * Containment: is $$L(A) \subseteq L(B)$$ ? Again, the variant of the problem where B is a regular grammar is decidable, while that where A is regular is generally not.
 * Universality: is $$L(A)=\Sigma^*$$?
 * Regularity: is $$L(A)$$ a regular language?
 * Ambiguity: is every grammar for $$L(A)$$ ambiguous?

The following problems are decidable for arbitrary context-free languages:
 * Emptiness: Given a context-free grammar A, is $$L(A) = \emptyset$$ ?
 * Finiteness: Given a context-free grammar A, is $$L(A)$$ finite?
 * Membership: Given a context-free grammar G, and a word $$w$$, does $$w \in L(G)$$ ? Efficient polynomial-time algorithms for the membership problem are the CYK algorithm and Earley's Algorithm.

According to Hopcroft, Motwani, Ullman (2003), many of the fundamental closure and (un)decidability properties of context-free languages were shown in the 1961 paper of Bar-Hillel, Perles, and Shamir

Languages that are not context-free
The set $$\{a^n b^n c^n d^n | n > 0\}$$ is a context-sensitive language, but there does not exist a context-free grammar generating this language. So there exist context-sensitive languages which are not context-free. To prove that a given language is not context-free, one may employ the pumping lemma for context-free languages or a number of other methods, such as Ogden's lemma or Parikh's theorem.

title: Context-free language