Unification modulo Synchronous Distributivity

Siva Anantharaman; Serdar Erbatur; Christopher Lynch; Paliath Narendran; Michael Rusinowitch

hal-00684185, version 1

Unification modulo Synchronous Distributivity

Siva Anantharaman (, ) ¹, Serdar Erbatur () ², Christopher Lynch ()^a^, 3, Paliath Narendran () ², Michael Rusinowitch () ⁴

IJCAR 2012 (The 6th International Joint Conference on Automated Reasoning) 7364 (2012) 14--29

Abstract: Unification modulo the theory defined by a single equation which specifies that a binary operator distributes synchronously over another binary operator is shown to be undecidable. It is the simplest known theory, to our knowledge, for which unification is undecidable: it has only one defining axiom and moreover, every congruence class is finite (so, the matching problem is decidable).

a – Clarkson University, Potsdam, NY (USA)
1: Laboratoire d'Informatique Fondamentale d'Orléans (LIFO)
Université d'Orléans : EA4022 – Ecole Nationale Supérieure d'Ingénieurs de Bourges
2: University at Albany
State university of New York
3: Computer Science Department [Potsdam NY]
Clarkson University, Potsdam NY (USA)
4: CASSIS (INRIA Nancy - Grand Est / LORIA / LIFC)
Université de Lorraine – Université de Franche-Comté – CNRS : FRE2661 – INRIA

hal-00684185, version 1
http://hal.archives-ouvertes.fr/hal-00684185
oai:hal.archives-ouvertes.fr:hal-00684185
From: Siva Anantharaman <>
Submitted on: Friday, 30 March 2012 17:36:37
Updated on: Monday, 8 April 2013 13:40:47

See detailed view

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="hal-00684185"><analytic>
<author><persName><forename>Siva</forename><surname>Anantharaman</surname></persName>
<affiliation>
<orgName type="laboratory">LIFO</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale d'Orléans</orgName>
<country>FR</country>
<orgName type="institution">Université d'Orléans : EA4022</orgName>
<orgName type="institution">Ecole Nationale Supérieure d'Ingénieurs de Bourges</orgName>
</affiliation>
</author>
<author><persName><forename>Serdar</forename><surname>Erbatur</surname></persName>
<affiliation>
<orgName type="team">University at Albany</orgName>
<country>US</country>
<orgName type="institution">State university of New York</orgName>
</affiliation>
</author>
<author><persName><forename>Christopher</forename><surname>Lynch</surname></persName>
<affiliation>
<orgName type="team">Computer Science Department [Potsdam NY]</orgName>
<country>US</country>
<orgName type="institution">Clarkson University, Potsdam NY (USA)</orgName>
</affiliation>
</author>
<author><persName><forename>Paliath</forename><surname>Narendran</surname></persName>
<affiliation>
<orgName type="team">University at Albany</orgName>
<country>US</country>
<orgName type="institution">State university of New York</orgName>
</affiliation>
</author>
<author><persName><forename>Michael</forename><surname>Rusinowitch</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Nancy - Grand Est / LORIA / LIFC</orgName>
<orgName type="team">CASSIS</orgName>
<country>FR</country>
<orgName type="institution">Université de Lorraine</orgName>
<orgName type="institution">Université de Franche-Comté</orgName>
<orgName type="institution">CNRS : FRE2661</orgName>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<title type="main" level="a">Unification modulo Synchronous Distributivity</title></analytic><monogr><title level="m" type="main">Lecture Notes in Artificial Intelligence</title><meeting>IJCAR 2012 (The 6th International Joint Conference on Automated Reasoning)</meeting><imprint><publisher>Springer-Verlag, Berlin, Heidelberg</publisher><pubPlace><settlement>Manchester</settlement><country>United Kingdom</country></pubPlace><biblScope type="publicationDate">2012-06-00</biblScope><biblScope type="vol">7364</biblScope><biblScope type="pp">14--29</biblScope></imprint></monogr><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00684185</idno></biblStruct>
</listBibl>
</listBibl>