6533b82efe1ef96bd1293c38
RESEARCH PRODUCT
Functions definable by numerical set-expressions
Ian Pratt-hartmannIvo Düntschsubject
FOS: Computer and information sciencesComputer Science - Logic in Computer ScienceLogic0102 computer and information sciences01 natural sciencesTheoretical Computer Scienceexpressive powerSet (abstract data type)integer expressionArts and Humanities (miscellaneous)Saturation arithmeticBoolean expression0101 mathematicsElectronic circuitMathematics010102 general mathematicsTerm (logic)Logic in Computer Science (cs.LO)AlgebraArithmetic circuitdefinability010201 computation theory & mathematicsHardware and ArchitectureCascadeAlgebraic operationMultiplicationF.1.1Softwaredescription
A "numerical set-expression" is a term specifying a cascade of arithmetic and logical operations to be performed on sets of non-negative integers. If these operations are confined to the usual Boolean operations together with the result of lifting addition to the level of sets, we speak of "additive circuits". If they are confined to the usual Boolean operations together with the result of lifting addition and multiplication to the level of sets, we speak of "arithmetic circuits". In this paper, we investigate the definability of sets and functions by means of additive and arithmetic circuits, occasionally augmented with additional operations.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2011-12-09 | Journal of Logic and Computation |