Related Research Articles
Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, the Boolean satisfiability problem (SAT), satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.
Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties from Prolog. It is often used as a query language for deductive databases. Datalog has been applied to problems in data integration, networking, program analysis, and more.
In the mathematical discipline of model theory, the Ehrenfeucht–Fraïssé game is a technique based on game semantics for determining whether two structures are elementarily equivalent. The main application of Ehrenfeucht–Fraïssé games is in proving the inexpressibility of certain properties in first-order logic. Indeed, Ehrenfeucht–Fraïssé games provide a complete methodology for proving inexpressibility results for first-order logic. In this role, these games are of particular importance in finite model theory and its applications in computer science, since Ehrenfeucht–Fraïssé games are one of the few techniques from model theory that remain valid in the context of finite models. Other widely used techniques for proving inexpressibility results, such as the compactness theorem, do not work in finite models.
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific abstract machines used to define them.
In formal logic, Horn-satisfiability, or HORNSAT, is the problem of deciding whether a given set of propositional Horn clauses is satisfiable or not. Horn-satisfiability and Horn clauses are named after Alfred Horn.
Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to interpretations on finite structures, which have a finite universe.
Paris Christos Kanellakis was a Greek American computer scientist.
Fagin's theorem is the oldest result of descriptive complexity theory, a branch of computational complexity theory that characterizes complexity classes in terms of logic-based descriptions of their problems rather than by the behavior of algorithms for solving those problems. The theorem states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP.
Data integration refers to the process of combining, sharing, or synchronizing data from multiple sources to provide users with a unified view. There are a wide range of possible applications for data integration, from commercial to scientific.
Moshe Ya'akov Vardi is an Israeli theoretical computer scientist. He is the Karen Ostrum George Distinguished Service Professor in Computational Engineering at Rice University, United States. and a faculty advisor for the Ken Kennedy Institute. His interests focus on applications of logic to computer science, including database theory, finite model theory, knowledge of multi-agent systems, computer-aided verification and reasoning, and teaching logic across the curriculum. He is an expert in model checking, constraint satisfaction and database theory, common knowledge (logic), and theoretical computer science.
In computational complexity theory, SNP is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties. It forms the basis for the definition of the class MaxSNP of optimization problems.
In database theory, a conjunctive query is a restricted form of first-order queries using the logical conjunction operator. Many first-order queries can be written as conjunctive queries. In particular, a large part of queries issued on relational databases can be expressed in this way. Conjunctive queries also have a number of desirable theoretical properties that larger classes of queries do not share.
Mihalis Yannakakis is a professor of computer science at Columbia University. He is noted for his work in computational complexity, databases, and other related fields. He won the Donald E. Knuth Prize in 2005.
In computer science, schema versioning and schema evolution, deal with the need to retain current data and software system functionality in the face of changing database structure. The problem is not limited to the modification of the schema. It, in fact, affects the data stored under the given schema and the queries posed on that schema.
Ronald Fagin is an American mathematician and computer scientist, and IBM Fellow at the IBM Almaden Research Center. He is known for his work in database theory, finite model theory, and reasoning about knowledge.
Georg Gottlob FRS is an Austrian-Italian computer scientist who works in the areas of database theory, logic, and artificial intelligence and is Professor of Informatics at the University of Calabria. He was Professor at the University of Oxford.
In mathematics and computer science, a pebble game is a type of mathematical game played by placing "pebbles" or "markers" on a directed acyclic graph according to certain rules:
ACM SIGLOG or SIGLOG is the Association for Computing Machinery Special Interest Group on Logic and Computation. It publishes a news magazine, and has the annual ACM–IEEE Symposium on Logic in Computer Science (LICS) as its flagship conference. In addition, it publishes an online newsletter, the SIGLOG Monthly Bulletin, and "maintains close ties" with the related academic journal ACM Transactions on Computational Logic.
Nicola Leone is an Italian computer scientist who works in the areas of artificial intelligence, knowledge representation and reasoning, and database theory. Leone is currently the rector of the University of Calabria and a professor of Computer Science. Previously, he was a professor of Database Systems at the TU Wien.
In databases and specifically in graph databases, a regular path query or RPQ is a query asking for pairs of endpoints in the database that are connected by a path satisfying a certain regular expression. A similar feature exists in the SPARQL query language as "property paths".
References
- ↑ "Curriculum Vitae. Phokion G. Kolaitis" (PDF).
- ↑ "Phokion Kolaitis Special Event at SIGMOD 2019".
- ↑ Fagin, Ronald; Kolaitis, Phokion G.; Miller, Renée J.; Popa, Lucian (25 May 2005). "Data exchange: semantics and query answering". Theoretical Computer Science. 336 (1): 89–124. doi: 10.1016/j.tcs.2004.10.033 . ISSN 0304-3975.
- ↑ Kolaitis, Phokion G.; Vardi, Moshe Y. (1 October 2000). "Conjunctive-Query Containment and Constraint Satisfaction". Journal of Computer and System Sciences. 61 (2): 302–332. doi: 10.1006/jcss.2000.1713 . ISSN 0022-0000.
- ↑ Fagin, Ronald; Kolaitis, Phokion G.; Popa, Lucian (1 March 2005). "Data exchange: getting to the core". ACM Transactions on Database Systems. 30 (1): 174–210. doi:10.1145/1061318.1061323. ISSN 0362-5915. S2CID 59942308.
- ↑ Fagin, Ronald; Kolaitis, Phokion G.; Popa, Lucian; Tan, Wang-Chiew (1 December 2005). "Composing schema mappings: Second-order dependencies to the rescue". ACM Transactions on Database Systems. 30 (4): 994–1055. doi:10.1145/1114244.1114249. ISSN 0362-5915. S2CID 5768010.
- ↑ Grädel, Erich; Kolaitis, Phokion G.; Vardi, Moshe Y. (1997). "On the Decision Problem for Two-Variable First-Order Logic". The Bulletin of Symbolic Logic. 3 (1): 53–69. doi:10.2307/421196. ISSN 1079-8986. JSTOR 421196. S2CID 14868390.
- ↑ "2005 ACM Fellows".
- ↑ "AAAS Fellows".
- ↑ "NKUA Doctorate".
- ↑ "2020 Alonzo Church Award".
