|
Kosaburo Hashiguchi
is a Japanese mathematician and computer scientist at the Toyohashi University of Technology and Okayama University, known for his research in formal language theory. In 1988, he found the first algorithm to determine the star height of a regular language, a problem that had been open since 1963 when Lawrence Eggan solved the related star height problem, showing that there is no finite bound on the star height. Hashiguchi's algorithm for star height is extremely complex, and impractical on all but the smallest examples. A simpler method, showing also that the problem is PSPACE-complete, was provided in 2005 by Kirsten. Earlier, in 1979, Hashiguchi had also solved another open problem on regular languages, of deciding whether, for a given language A, there exists a finite number n such that A^n=A^*. Hashiguchi is the uncle of Japanese-born American pianist Grace Nikae. Selected publications References External linksHome page {{DEFAULTSORT:Hashiguchi, Kosaburo Year of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Toyohashi University Of Technology
Toyohashi University of Technology (豊橋技術科学大学; ''Toyohashi Gijutsu Kagaku Daigaku''), often abbreviated to Toyohashi Tech, or TUT, is a national engineering university located in Toyohashi, Aichi, Japan. Distinguished for the upper-division student body where over 80% of them are transfer students from 5-year Technical Colleges called ''Kōsens'', the Toyohashi Tech is one of the only two Universities of Technology, a form of universities in Japan, the other being Nagaoka University of Technology. Toyohashi Tech is also noted for the fact that majority of the students proceed to graduate schools. The university is locally nicknamed ''Gikadai'' (技科大). History Toyohashi University of Technology was founded on October 1, 1976, after the government’s decision to establish the Graduate School of Science and Technology in Toyohashi city in 1974. This is based on the request from Japanese National Technical Colleges, to the Minister of Education in 1972. Or ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Okayama University
is a national university in Japan. The main campus is located in Tsushima-Naka, Okayama, Okayama Prefecture. The school was founded in 1870 and it was established as a university in 1949. History Okayama University was originally founded as the in 1870 by Okayama-Han. After the abolition of the han system, it became the in 1880. In 1888 it was merged into a national school, to constitute the Medical Faculty. The Medical Faculty became an independent school in 1901 and was renamed , a four-year medical school for men ages 17–21 or above. In 1922, the school was chartered as , a four-year medical college for men ages 19–23 or above. In 1949, after World War II, the college was merged with other national and public colleges in Okayama Prefecture to establish Okayama University, under Japan's new education system. The predecessors of the university were Okayama Medical College, , , and . The new campus (Tsushima Campus) was the former camp of the Imperial Japanese Army ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Formal Language
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. The alphabet of a formal language consists of symbols, letters, or tokens that concatenate into strings of the language. Each string concatenated from symbols of this alphabet is called a word, and the words that belong to a particular formal language are sometimes called ''well-formed words'' or ''well-formed formulas''. A formal language is often defined by means of a formal grammar such as a regular grammar or context-free grammar, which consists of its formation rules. In computer science, formal languages are used among others as the basis for defining the grammar of programming languages and formalized versions of subsets of natural languages in which the words of the language represent concepts that are associated with particular meanings or semantics. In computational complexity ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can perform automated deductions (referred to as automated reasoning) and use mathematical and logical tests to divert the code execution through various routes (referred to as automated decision-making). Using human characteristics as descriptors of machines in metaphorical ways was already practiced by Alan Turing with terms such as "memory", "search" and "stimulus". In contrast, a Heuristic (computer science), heuristic is an approach to problem solving that may not be fully specified or may not guarantee correct or optimal results, especially in problem domains where there is no well-defined correct or optimal result. As an effective method, an algorithm ca ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Star Height
In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexity of regular expressions and regular languages. The star height of a regular ''expression'' equals the maximum nesting depth of stars appearing in that expression. The star height of a regular ''language'' is the least star height of any regular expression for that language. The concept of star height was first defined and studied by Eggan (1963). Formal definition More formally, the star height of a regular expression ''E'' over a finite alphabet ''A'' is inductively defined as follows: * \textstyle h\left(\emptyset\right)\,=\,0, \textstyle h\left(\varepsilon\right)\,=\,0, and \textstyle h\left(a\right)\,=\,0 for all alphabet symbols ''a'' in ''A''. * \textstyle h\left(E F\right)\,=\, h\left(E\, \mid\, F\right)\,=\,\max \left(\, h(E), h(F)\,\right) * \textstyle h\left(E^*\right)\,=\,h(E)+1. Here, \scriptstyle \emptyset is the special regular ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regular Language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expressions engines, which are augmented with features that allow recognition of non-regular languages). Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleene's theorem (after American mathematician Stephen Cole Kleene). In the Chomsky hierarchy, regular languages are the languages generated by Type-3 grammars. Formal definition The collection of regular languages over an alphabet Σ is defined recursively as follows: * The empty language Ø is a regular language. * For each ''a'' ∈ Σ (''a'' belongs to Σ), the singleton language is a regular language. * If ''A'' is a regular language, ''A''* ( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Star Height Problem
The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of one always sufficient? If not, is there an algorithm to determine how many are required? The problem was raised by . Families of regular languages with unbounded star height The first question was answered in the negative when in 1963, Eggan gave examples of regular languages of star height ''n'' for every ''n''. Here, the star height ''h''(''L'') of a regular language ''L'' is defined as the minimum star height among all regular expressions representing ''L''. The first few languages found by are described in the following, by means of giving a regular expression for each language: :\begin e_1 &= a_1^* \\ e_2 &= \left(a_1^*a_2^*a_3\right)^*\\ e_3 &= \left(\left(a_1^*a_2^*a_3\right)^*\left(a_4^*a_5^*a_6\right)^*a_7\right)^*\\ e_4 &= ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
PSPACE-complete
In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. Problems known to be PSPACE-complete include determining properties of regular expressions and context-sensitive grammars, determining the truth of quantified Boolean formulas, step-by-step changes between solutions of combinatorial optimization problems, and many puzzles and games. Theory A problem is defined to be PSPACE-complete if it can be solved using a polynomial amount of memory (it belongs to PSPACE) and every problem in PSPACE can be tr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Grace Nikae
Grace Nikae (born in Kagoshima, Japan) is an American classical pianist. At the age of 3 months, she moved to Honolulu, Hawaii and grew up in Aiea. She was raised by her mother, Kazuko Hashiguchi, who is a teacher.Moniz, Melissa: "Born to Play the Piano", ''Midweek'', November 17, 2004 Her uncle, Kosaburo Hashiguchi, is a Japanese mathematician who solved the remaining star height problem. A child prodigy, Nikae started to learn the piano from her mother at nine months old, and performed her first public performance at age three. At the age of four, she was featured on television performing a concerto by Haydn. Her debut with orchestra came at age eight, when she performed Mozart's Concerto No. 14 KV 449 with the Honolulu Symphony Orchestra. She made her international recital debut in Japan at the age of thirteen.Fischer, Tobia"15 Questions to Grace Nikae" ''Tokafi'', June 6, 2005. Accessed January 7, 2020. Upon graduation from Iolani School, Nikae moved to New York City. She ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Science (journal)
''Theoretical Computer Science'' (TCS) is a computer science journal published by Elsevier, started in 1975 and covering theoretical computer science. The journal publishes 52 issues a year. It is abstracted and indexed by Scopus and the Science Citation Index. According to the Journal Citation Reports, its 2020 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a scientometric index calculated by Clarivate that reflects the yearly mean number of citations of articles published in the last two years in a given journal, as i ... is 0.827. References Computer science journals Elsevier academic journals Publications established in 1975 {{comp-sci-theory-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Information And Computation
''Information and Computation'' is a closed-access computer science journal published by Elsevier (formerly Academic Press). The journal was founded in 1957 under its former name ''Information and Control'' and given its current title in 1987. , the current editor-in-chief is David Peleg. The journal publishes 12 issues a year. History ''Information and Computation'' was founded as ''Information and Control'' in 1957 at the initiative of Leon Brillouin and under the editorship of Leon Brillouin, Colin Cherry and Peter Elias. Murray Eden joined as editor in 1962 and became sole editor-in-chief in 1967. He was succeeded by Albert R. Meyer in 1981, under whose editorship the journal was rebranded ''Information and Computation'' in 1987 in response to the shifted focus of the journal towards theory of computation and away from control theory. In 2020, Albert Mayer was succeeded by David Peleg as editor-in-chief of the journal. Indexing All articles from the ''Information and Comput ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Year Of Birth Missing (living People)
A year or annus is the orbital period of a planetary body, for example, the Earth, moving in its orbit around the Sun. Due to the Earth's axial tilt, the course of a year sees the passing of the seasons, marked by change in weather, the hours of daylight, and, consequently, vegetation and soil fertility. In temperate and subpolar regions around the planet, four seasons are generally recognized: spring, summer, autumn and winter. In tropical and subtropical regions, several geographical sectors do not present defined seasons; but in the seasonal tropics, the annual wet and dry seasons are recognized and tracked. A calendar year is an approximation of the number of days of the Earth's orbital period, as counted in a given calendar. The Gregorian calendar, or modern calendar, presents its calendar year to be either a common year of 365 days or a leap year of 366 days, as do the Julian calendars. For the Gregorian calendar, the average length of the calendar year (the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
