In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules called a formal grammar.
In theoretical computer science and formal language theory, a regular language is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science.
In formal language theory, a noncontracting grammar is in Kuroda normal form if all production rules are of the form:
The European Association for Theoretical Computer Science (EATCS) is an international organization with a European focus, founded in 1972. Its aim is to facilitate the exchange of ideas and results among theoretical computer scientists as well as to stimulate cooperation between the theoretical and the practical community in computer science.
ICALP, the International Colloquium on Automata, Languages, and Programming is an academic conference organized annually by the European Association for Theoretical Computer Science and held in different locations around Europe. Like most theoretical computer science conferences its contributions are strongly peer-reviewed. The articles have appeared in proceedings published by Springer in their Lecture Notes in Computer Science, but beginning in 2016 they are instead published by the Leibniz International Proceedings in Informatics.
Jarkko J. Kari is a Finnish mathematician and computer scientist, known for his contributions to the theory of Wang tiles and cellular automata. Kari is currently a professor at the Department of Mathematics, University of Turku.
In computer science, in particular in the field of formal language theory, an abstract family of languages is an abstract mathematical notion generalizing characteristics common to the regular languages, the context-free languages and the recursively enumerable languages, and other families of formal languages studied in the scientific literature.
In formal language theory, a grammar is noncontracting if for all of its production rules, α → β, it holds that |α| ≤ |β|, that is β has at least as many symbols as α. A grammar is essentially noncontracting if there may be one exception, namely, a rule S → ε where S is the start symbol and ε the empty string, and furthermore, S never occurs in the right-hand side of any rule.
Andrzej Ehrenfeucht is a Polish-American mathematician and computer scientist.
In formal language theory, a cone is a set of formal languages that has some desirable closure properties enjoyed by some well-known sets of languages, in particular by the families of regular languages, context-free languages and the recursively enumerable languages. The concept of a cone is a more abstract notion that subsumes all of these families. A similar notion is the faithful cone, having somewhat relaxed conditions. For example, the context-sensitive languages do not form a cone, but still have the required properties to form a faithful cone.
DLT, the International Conference on Developments in Language Theory is an academic conference in the field of computer science held annually under the auspices of the European Association for Theoretical Computer Science. Like most theoretical computer science conferences its contributions are strongly peer-reviewed; the articles appear in proceedings published in Springer Lecture Notes in Computer Science. Extended versions of selected papers of each year's conference appear in international journals, such as Theoretical Computer Science and International Journal of Foundations of Computer Science.
Wilfried Brauer was a German computer scientist and professor emeritus at Technical University of Munich.
Janusz (John) Antoni Brzozowski was a Polish-Canadian computer scientist and Distinguished Professor Emeritus at the University of Waterloo's David R. Cheriton School of Computer Science.
Grzegorz Rozenberg is a Polish and Dutch computer scientist.
In mathematics, a local language is a formal language for which membership of a word in the language can be determined by looking at the first and last symbol and each two-symbol substring of the word. Equivalently, it is a language recognised by a local automaton, a particular kind of deterministic finite automaton.
Nataša Jonoska is a Macedonian mathematician and professor at the University of South Florida known for her work in DNA computing. Her research is about how biology performs computation, "in particular using formal models such as cellular or other finite types of automata, formal language theory symbolic dynamics, and topological graph theory to describe molecular computation."
Kai Tapani Salomaa is a Finnish Canadian theoretical computer scientist, known for his numerous contributions to the state complexity of finite automata. His highly cited 1994 joint paper with Yu and Zhuang laid the foundations of the area. He has published over 100 papers in scientific journals on various subjects in formal language theory. Salomaa is a full professor at Queen's University.
Jean-Éric Pin is a French mathematician and theoretical computer scientist known for his contributions to the algebraic automata theory and semigroup theory. He is a CNRS research director.
Derick Wood (1940–2010) was an English computer scientist who worked for many years as a professor of computer science in Canada and Hong Kong. He was known for his research in automata theory and formal languages, much of which he published in collaboration with Hermann Maurer and Arto Salomaa, and also for his work in computational geometry.
Hartmut Ehrig was a German computer scientist and professor of theoretical computer science and formal specification. He was a pioneer in algebraic specification of abstract data types, and in graph grammars.
