On the Succinctness of Cardinality Constraint Programs and Canonical Logic Programs
| Autor: | Yan Zhang, Fasheng Cao |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Constraint (information theory)
Discrete mathematics Ping (video games) Succinctness Computer science Parity problem 020204 information systems ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Cardinality (SQL statements) 02 engineering and technology Translation (geometry) |
| Zdroj: | ISCID (1) |
| DOI: | 10.1109/iscid.2019.00062 |
| Popis: | In this paper, we will discuss the succinctness between cardinality constraint programs (CPing) and canonical logic programs (Ping). We prove that every Ping program has an equivalent translation in CPing with small-size growth(without new variables). It is well known that the PARITY problem can be represented by a polynomial-size CPing program while exponential-size blowup is inevitable in Ping programs(without new variables). we get the conclusion that CPing is more succinct than Ping. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|