Log in

Relevant bibliographies by topics / Inductive types / Journal articles

Journal articles on the topic 'Inductive types'

To see the other types of publications on this topic, follow the link: Inductive types.

Author: Grafiati

Published: 11 March 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Inductive types.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Kaposi, Ambrus, András Kovács, and Thorsten Altenkirch. "Constructing quotient inductive-inductive types." Proceedings of the ACM on Programming Languages 3, POPL (January 2, 2019): 1–24. http://dx.doi.org/10.1145/3290315.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Barthe, Gilles. "Order-Sorted Inductive Types." Information and Computation 149, no. 1 (February 1999): 42–76. http://dx.doi.org/10.1006/inco.1998.2751.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

DE ANGELIS, EMANUELE, FABIO FIORAVANTI, ALBERTO PETTOROSSI, and MAURIZIO PROIETTI. "Solving Horn Clauses on Inductive Data Types Without Induction." Theory and Practice of Logic Programming 18, no. 3-4 (July 2018): 452–69. http://dx.doi.org/10.1017/s1471068418000157.

Full text

Abstract:

AbstractWe address the problem of verifying the satisfiability of Constrained Horn Clauses (CHCs) based on theories of inductively defined data structures, such as lists and trees. We propose a transformation technique whose objective is the removal of these data structures from CHCs, hence reducing their satisfiability to a satisfiability problem for CHCs on integers and booleans. We propose a transformation algorithm and identify a class of clauses where it always succeeds. We also consider an extension of that algorithm, which combines clause transformation with reasoning on integer constraints. Via an experimental evaluation we show that our technique greatly improves the effectiveness of applying the Z3 solver to CHCs. We also show that our verification technique based on CHC transformation followed by CHC solving, is competitive with respect to CHC solvers extended with induction.

APA, Harvard, Vancouver, ISO, and other styles

4

Howard, Brian T. "Inductive, coinductive, and pointed types." ACM SIGPLAN Notices 31, no. 6 (June 15, 1996): 102–9. http://dx.doi.org/10.1145/232629.232640.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

LUMSDAINE, PETER LEFANU, and MICHAEL SHULMAN. "Semantics of higher inductive types." Mathematical Proceedings of the Cambridge Philosophical Society 169, no. 1 (June 17, 2019): 159–208. http://dx.doi.org/10.1017/s030500411900015x.

Full text

Abstract:

AbstractHigher inductive typesare a class of type-forming rules, introduced to provide basic (and not-so-basic) homotopy-theoretic constructions in a type-theoretic style. They have proven very fruitful for the “synthetic” development of homotopy theory within type theory, as well as in formalising ordinary set-level mathematics in type theory. In this paper, we construct models of a wide range of higher inductive types in a fairly wide range of settings.We introduce the notion ofcell monad with parameters: a semantically-defined scheme for specifying homotopically well-behaved notions of structure. We then show that any suitable model category hasweakly stable typal initial algebrasfor any cell monad with parameters. When combined with the local universes construction to obtain strict stability, this specialises to give models of specific higher inductive types, including spheres, the torus, pushout types, truncations, the James construction and general localisations.Our results apply in any sufficiently nice Quillen model category, including any right proper, simplicially locally cartesian closed, simplicial Cisinski model category (such as simplicial sets) and any locally presentable locally cartesian closed category (such as sets) with its trivial model structure. In particular, any locally presentable locally cartesian closed (∞, 1)-category is presented by some model category to which our results apply.

APA, Harvard, Vancouver, ISO, and other styles

6

Loader, Ralph. "Equational theories for inductive types." Annals of Pure and Applied Logic 84, no. 2 (March 1997): 175–217. http://dx.doi.org/10.1016/s0168-0072(96)00021-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

OGATA, K., and K. FUTATSUGI. "State Machines as Inductive Types." IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E90-A, no. 12 (December 1, 2007): 2985–88. http://dx.doi.org/10.1093/ietfec/e90-a.12.2985.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

van den Berg, Benno. "Inductive types and exact completion." Annals of Pure and Applied Logic 134, no. 2-3 (July 2005): 95–121. http://dx.doi.org/10.1016/j.apal.2004.09.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

ABEL, ANDREAS. "Implementing a normalizer using sized heterogeneous types." Journal of Functional Programming 19, no. 3-4 (July 2009): 287–310. http://dx.doi.org/10.1017/s0956796809007266.

Full text

Abstract:

AbstractIn the simply typed λ-calculus, a hereditary substitution replaces a free variable in a normal formrby another normal formsof typea, removing freshly created redexes on the fly. It can be defined by lexicographic induction onaandr, thus giving rise to a structurally recursive normalizer for the simply typed λ-calculus. We implement hereditary substitutions in a functional programming language with sized heterogeneous inductive types$\Fhat$, arriving at an interpreter whose termination can be tracked by the type system of its host programming language.

APA, Harvard, Vancouver, ISO, and other styles

10

Matthes, Ralph. "Monotone (co)inductive types and positive fixed-point types." RAIRO - Theoretical Informatics and Applications 33, no. 4-5 (July 1999): 309–28. http://dx.doi.org/10.1051/ita:1999120.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

DE ANGELIS, EMANUELE, FABIO FIORAVANTI, ALBERTO PETTOROSSI, and MAURIZIO PROIETTI. "Solving Horn Clauses on Inductive Data Types Without Induction – ERRATUM." Theory and Practice of Logic Programming 19, no. 04 (May 27, 2019): 629. http://dx.doi.org/10.1017/s147106841900005x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Fu, Yuxi. "RECURSIVE MODELS OF GENERAL INDUCTIVE TYPES." Fundamenta Informaticae 26, no. 2 (1996): 115–31. http://dx.doi.org/10.3233/fi-1996-26202.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Filinski, Andrzej, and Kristian Støvring. "Inductive reasoning about effectful data types." ACM SIGPLAN Notices 42, no. 9 (October 2007): 97–110. http://dx.doi.org/10.1145/1291220.1291168.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Moor, Oege de. "Inductive data types for predicate transformers." Information Processing Letters 43, no. 3 (September 1992): 113–17. http://dx.doi.org/10.1016/0020-0190(92)90001-c.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Barthe, Gilles, and Tarmo Uustalu. "CPS translating inductive and coinductive types." ACM SIGPLAN Notices 37, no. 3 (March 2002): 131–42. http://dx.doi.org/10.1145/509799.503043.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Sojakova, Kristina. "Higher Inductive Types as Homotopy-Initial Algebras." ACM SIGPLAN Notices 50, no. 1 (May 11, 2015): 31–42. http://dx.doi.org/10.1145/2775051.2676983.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Chemouil, David, and Sergei Soloviev. "Remarks on Isomorphisms of Simple Inductive Types." Electronic Notes in Theoretical Computer Science 85, no. 7 (September 2003): 106–24. http://dx.doi.org/10.1016/s1571-0661(04)80760-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Tan, Qingping. "A higher-order unification algorithm for inductive types and dependent types." Journal of Computer Science and Technology 12, no. 3 (May 1997): 231–43. http://dx.doi.org/10.1007/bf02948973.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

LUO, ZHAOHUI, and ROBIN ADAMS. "Structural subtyping for inductive types with functorial equality rules." Mathematical Structures in Computer Science 18, no. 5 (October 2008): 931–72. http://dx.doi.org/10.1017/s0960129508006956.

Full text

Abstract:

In this paper we study subtyping for inductive types in dependent type theories in the framework of coercive subtyping. General structural subtyping rules for parameterised inductive types are formulated based on the notion of inductive schemata. Certain extensional equality rules play an important role in proving some of the crucial properties of the type system with these subtyping rules. In particular, it is shown that the structural subtyping rules are coherent and that transitivity is admissible in the presence of the functorial rules of computational equality.

APA, Harvard, Vancouver, ISO, and other styles

20

Slee, Bill. "An inductive classification of types of social innovation." Scottish Affairs 28, no. 2 (May 2019): 152–76. http://dx.doi.org/10.3366/scot.2019.0275.

Full text

Abstract:

Though widely regarded as ill-defined and lacking conceptual clarity, social innovation has been heralded as a desirable response to social economic and environmental challenges arising from market and policy failures. Based on a definition of social innovation as involving the reconfiguration of social practices through civil society engagement, this paper offers an inductive classification of the diverse types of social innovation found in Scotland, based primarily on rural examples. It is argued that not only does social innovation occur in a diverse range of fields and in many different forms, but also that the Scottish Government policy has explicitly connected to social innovation as a means of delivering a communitarian policy agenda. However, without affirmative action, the community empowerment agenda is likely to widen the gap between communities with strong social capital and those with weaker social capital, thus undermining another strong strand of Scottish policy which supports greater equality and social inclusion.

APA, Harvard, Vancouver, ISO, and other styles

21

Al-Sibahi, Ahmad Salim, Thomas P. Jensen, Aleksandar S. Dimovski, and Andrzej Wąsowski. "Verification of Program Transformations with Inductive Refinement Types." ACM Transactions on Software Engineering and Methodology 30, no. 1 (January 21, 2021): 1–33. http://dx.doi.org/10.1145/3409805.

Full text

Abstract:

High-level transformation languages like Rascal include expressive features for manipulating large abstract syntax trees: first-class traversals, expressive pattern matching, backtracking, and generalized iterators. We present the design and implementation of an abstract interpretation tool, Rabit, for verifying inductive type and shape properties for transformations written in such languages. We describe how to perform abstract interpretation based on operational semantics, specifically focusing on the challenges arising when analyzing the expressive traversals and pattern matching. Finally, we evaluate Rabit on a series of transformations (normalization, desugaring, refactoring, code generators, type inference, etc.) showing that we can effectively verify stated properties.

APA, Harvard, Vancouver, ISO, and other styles

22

Basold, Henning. "Dependent Inductive and Coinductive Types are Fibrational Dialgebras." Electronic Proceedings in Theoretical Computer Science 191 (September 9, 2015): 3–17. http://dx.doi.org/10.4204/eptcs.191.3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Cavallo, Evan, and Robert Harper. "Higher inductive types in cubical computational type theory." Proceedings of the ACM on Programming Languages 3, POPL (January 2, 2019): 1–27. http://dx.doi.org/10.1145/3290314.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

CHEMOUIL, DAVID. "Isomorphisms of simple inductive types through extensional rewriting." Mathematical Structures in Computer Science 15, no. 05 (October 4, 2005): 875. http://dx.doi.org/10.1017/s0960129505004950.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Dybjer, Peter, and Hugo Moeneclaey. "Finitary Higher Inductive Types in the Groupoid Model." Electronic Notes in Theoretical Computer Science 336 (April 2018): 119–34. http://dx.doi.org/10.1016/j.entcs.2018.03.019.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

van der Weide, Niels, and Herman Geuvers. "The Construction of Set-Truncated Higher Inductive Types." Electronic Notes in Theoretical Computer Science 347 (November 2019): 261–80. http://dx.doi.org/10.1016/j.entcs.2019.09.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Vezzosi, Andrea, Anders Mörtberg, and Andreas Abel. "Cubical agda: a dependently typed programming language with univalence and higher inductive types." Proceedings of the ACM on Programming Languages 3, ICFP (July 26, 2019): 1–29. http://dx.doi.org/10.1145/3341691.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

MORRIS, PETER, THORSTEN ALTENKIRCH, and NEIL GHANI. "A UNIVERSE OF STRICTLY POSITIVE FAMILIES." International Journal of Foundations of Computer Science 20, no. 01 (February 2009): 83–107. http://dx.doi.org/10.1142/s0129054109006462.

Full text

Abstract:

In order to represent, compute and reason with advanced data types like lists with a fixed length, finite sets or well scoped λ-terms one must go beyond the traditional treatment of data types as being inductive types and, instead, consider them as inductive families, or more precisely Strictly Positive Families (SPFs). We have previously shown that the grammar of strictly positive types (SPT) can be given as an inductively defined family. In the present paper we go one step further an show that the universe of SPFs can be encoded as an SPF. We show that SPFs can be used to represent and compute with a variety of advanced data types and that generic programs can be naturally written over the universe of SPFs.

APA, Harvard, Vancouver, ISO, and other styles

29

Levinsohn, Stephen H. "Reasoning Styles and Types of Hortatory Discourse." Journal of Translation 2, no. 2 (2006): 1–10. http://dx.doi.org/10.54395/jot-8pnhv.

Full text

Abstract:

This paper presents a modification of the types of supportive information that Breeze (1992) identified for hortatory discourses as a basis for bringing out the mismatches that are most likely to occur when translating from a verb-object (VO) language to an object-verb (OV) language. Earlier sections review the factors that underlie Longacre's (1996) classification of texts into four broad categories and outline what characterizes mainline information for each genre. They are followed by illustrations of deductive and inductive reasoning from Koiné Greek and Ancient Hebrew, since deductive reasoning tends to correlate with instructional exhortations and inductive reasoning with attempts to persuade.

APA, Harvard, Vancouver, ISO, and other styles

30

Botting, David. "Two Types of Argument from Position to Know." Informal Logic 38, no. 4 (December 18, 2018): 502–30. http://dx.doi.org/10.22329/il.v38i4.5065.

Full text

Abstract:

In this paper I will argue that there is an inductive and a non-inductive argument from position to know, and will characterise the latter as an argument from (epistemic) authority because of providing content-independent reasons. I will also argue that both types of argument should be doubt-preserving: testimony cannot justify a stronger cognitive attitude in the arguer than the expert herself expresses when she testifies. Failure to appreciate this point undercuts Mizrahi’s (2013) claim that arguments from expert opinion are weak.

APA, Harvard, Vancouver, ISO, and other styles

31

HOOGENDIJK, PAUL, and OEGE DE MOOR. "Container types categorically." Journal of Functional Programming 10, no. 2 (March 2000): 191–225. http://dx.doi.org/10.1017/s0956796899003640.

Full text

Abstract:

A program derivation is said to be polytypic if some of its parameters are data types. Often these data types are container types, whose elements store data. Polytypic program derivations necessitate a general, non-inductive definition of ‘container (data) type’. Here we propose such a definition: a container type is a relator that has membership. It is shown how this definition implies various other properties that are shared by all container types. In particular, all container types have a unique strength, and all natural transformations between container types are strong.

APA, Harvard, Vancouver, ISO, and other styles

32

Samran, Santalunai, Thosdeekoraphat Thanaset, and Thongsopa Chanchai. "Thermal Analysis of Inductive Coils Array against Cylindrical Material Steel for Induction Heating Applications." Applied Mechanics and Materials 330 (June 2013): 754–59. http://dx.doi.org/10.4028/www.scientific.net/amm.330.754.

Full text

Abstract:

This paper presented the heating of inductive coil which is 3 elements array. The induction heating coil improve the variations heating that it is increased the system efficiency. By means of the inductive coil has the diameter of 2, 3 and 4 cm and divide the coil as 2 types. There are the inverses and reverse inductive coil arrays, with heating test by cylindrical steel material. Then, this paper considers the heating efficiency simulation of 2 types by CST EM studio 2009. In addition, the experimental of the inductor heating is use the full bridge inverter circuit, the power of 200 W at 28 kHz resonant frequency. Moreover, the distance between coils is coincided of simulation and experimental results, the inverse type at the diameter of 2 cm can be provide the maximum heater.

APA, Harvard, Vancouver, ISO, and other styles

33

Miao, Decheng, Jianqing Xi, Yubin Guo, and Deyou Tang. "Inductive Data Types Based on Fibrations Theory in Programming." Journal of Computing and Information Technology 24, no. 1 (March 25, 2016): 1–16. http://dx.doi.org/10.20532/cit.2016.1002716.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Altenkirch, Thorsten, and Ambrus Kaposi. "Type theory in type theory using quotient inductive types." ACM SIGPLAN Notices 51, no. 1 (April 8, 2016): 18–29. http://dx.doi.org/10.1145/2914770.2837638.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Al-Sibahi, Ahmad Salim, Thomas P. Jensen, Aleksandar S. Dimovski, and Andrzej Wąsowski. "Verification of high-level transformations with inductive refinement types." ACM SIGPLAN Notices 53, no. 9 (April 7, 2020): 147–60. http://dx.doi.org/10.1145/3393934.3278125.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Danner, Norman, Daniel R. Licata, and Ramyaa Ramyaa. "Denotational cost semantics for functional languages with inductive types." ACM SIGPLAN Notices 50, no. 9 (December 18, 2015): 140–51. http://dx.doi.org/10.1145/2858949.2784749.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Ore, Christian-Emil. "The Extended Calculus of Constructions (ECC) with inductive types." Information and Computation 99, no. 2 (August 1992): 231–64. http://dx.doi.org/10.1016/0890-5401(92)90031-a.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Devesas Campos, Marco, and Marcelo Fiore. "Classical logic with Mendler induction." Journal of Logic and Computation 30, no. 1 (January 2020): 77–106. http://dx.doi.org/10.1093/logcom/exaa004.

Full text

Abstract:

Abstract We investigate (co-) induction in classical logic under the propositions-as-types paradigm, considering propositional, second-order and (co-) inductive types. Specifically, we introduce an extension of the Dual Calculus with a Mendler-style (co-) iterator and show that it is strongly normalizing. We prove this using a reducibility argument.

APA, Harvard, Vancouver, ISO, and other styles

39

ABEL, ANDREAS. "Polarised subtyping for sized types." Mathematical Structures in Computer Science 18, no. 5 (October 2008): 797–822. http://dx.doi.org/10.1017/s0960129508006853.

Full text

Abstract:

We present an algorithm for deciding polarised higher-order subtyping without bounded quantification. Constructors are identified not only modulo β, but also η. We give a direct proof of completeness, without constructing a model or establishing a strong normalisation theorem. Inductive and coinductive types are enriched with a notion of size and the subtyping calculus is extended to account for the inclusions arising between the sized types.

APA, Harvard, Vancouver, ISO, and other styles

40

BERGER, ULRICH, and TIE HOU. "A realizability interpretation of Church's simple theory of types." Mathematical Structures in Computer Science 27, no. 8 (July 22, 2016): 1364–85. http://dx.doi.org/10.1017/s0960129516000104.

Full text

Abstract:

We give a realizability interpretation of an intuitionistic version of Church's Simple Theory of Types (CST) which can be viewed as a formalization of intuitionistic higher-order logic. Although definable in CST we include operators for monotone induction and coinduction and provide simple realizers for them. Realizers are formally represented in an untyped lambda–calculus with pairing and case-construct. The purpose of this interpretation is to provide a foundation for the extraction of verified programs from formal proofs as an alternative to type-theoretic systems. The advantages of our approach are that (a) induction and coinduction are not restricted to the strictly positive case, (b) abstract mathematical structures and results may be imported, (c) the formalization is technically simpler than in other systems, for example, regarding the definition of realizability, which is a simple syntactical substitution, and the treatment of nested and simultaneous (co)inductive definitions.

APA, Harvard, Vancouver, ISO, and other styles

41

VAN DEN BERG, BENNO, and IEKE MOERDIJK. "W-types in homotopy-type theory – CORRIGENDUM." Mathematical Structures in Computer Science 28, no. 1 (April 5, 2016): 140. http://dx.doi.org/10.1017/s0960129516000025.

Full text

Abstract:

In the article below, Theorem 3.4 requires the additional assumption that A is Kan as well. Indeed, the inductive proof as given only shows that if W(f)<α is a Kan complex, then W(f)<α+1 → A is a Kan fibration.

APA, Harvard, Vancouver, ISO, and other styles

42

Wanko, Jeffrey J. "Teaching Inductive Reasoning with Puzzles." Mathematics Teacher 110, no. 7 (March 2017): 514–19. http://dx.doi.org/10.5951/mathteacher.110.7.0514.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Seehase, Dirk, Christian Kohlen, Arne Neiser, Andrej Novikov, and Mathias Nowottnick. "Selective Soldering on Printed Circuit Boards with Endogenous Induction Heat at Appropriate Susceptors." Periodica Polytechnica Electrical Engineering and Computer Science 62, no. 4 (November 30, 2018): 172–80. http://dx.doi.org/10.3311/ppee.13277.

Full text

Abstract:

In this work, methods for the endogenous heating of printed circuit boards (PCBs) by means of inductive losses in built-in susceptors are presented. Two basic types of inductive heating were studied, the heating in the transversal field and the heating in the longitudinal field. Elementary test stands were constructed and characterized for both field geometries. These setups were then used to analyze various susceptor materials like copper and aluminum for the transversal field heating and nickel and iron for the longitudinal field heating. To demonstrate the soldering processes by means of inductive heating, exemplary processes were conducted on both test stands by emulating a standard solder reflow profile. The limitations of using induction heating on printed circuit boards are illustrated by component lead frames, which also heat up in the inductive field and can hence be damaged.In short, this paper presents a selective heating method, based on induction heating, for printed circuit boards. Furthermore possible setups for implementing this heating method are described.

APA, Harvard, Vancouver, ISO, and other styles

44

Ripka, Pavel, Josef Blažek, Mehran Mirzaei, Pavol Lipovský, Miroslav Šmelko, and Katarína Draganová. "Inductive Position and Speed Sensors." Sensors 20, no. 1 (December 21, 2019): 65. http://dx.doi.org/10.3390/s20010065.

Full text

Abstract:

Magnetic position and speed sensors are rugged and durable. While DC magnetic sensors use permanent magnets as a field source and usually have only mm or cm range, inductive sensors use electromagnetic induction and they may work up to a distance of 20 m. Eddy current inductive sensors equipped with magnetoresistive sensors instead of inductive coils can operate at low frequencies, allowing detection through a conductive wall. In this paper, we make an overview of existing systems and we present new results in eddy current velocity and position measurements. We also present several types of inductive position sensors developed in our laboratories for industrial applications in pneumatic and hydraulic cylinders, underground drilling, large mining machines, and for detecting ferromagnetic objects on conveyors. While the most precise inductive position sensors have a resolution of 10 nm and linearity of 0.2%, precision requirements on the industrial sensors which we develop are less demanding, but they should have large working distance and large resistance to environmental conditions and interference.

APA, Harvard, Vancouver, ISO, and other styles

45

De Angelis, Emanuele, Fabio Fioravanti, Alberto Pettorossi, and Maurizio Proietti. "Satisfiability of constrained Horn clauses on algebraic data types: A transformation-based approach." Journal of Logic and Computation 32, no. 2 (February 4, 2022): 402–42. http://dx.doi.org/10.1093/logcom/exab090.

Full text

Abstract:

Abstract We address the problem of checking the satisfiability of constrained Horn clauses (CHCs) defined on algebraic data types (ADTs), such as lists and trees. We propose a new technique for transforming CHCs defined on ADTs into CHCs where the arguments of the predicates have only basic types, such as integers and booleans. Thus, our technique avoids, during satisfiability checking, the explicit use of proof rules based on induction over the ADTs. The main extension over previous techniques for ADT removal is a new transformation rule, called differential replacement, which allows us to introduce auxiliary predicates, whose definitions correspond to lemmas that are used when making inductive proofs. We present an algorithm that performs the automatic removal of ADTs by applying the new rule, together with the traditional folding/unfolding rules. We prove that, under suitable hypotheses, the set of the transformed clauses is satisfiable if and only if so is the set of the original clauses. By an experimental evaluation, we show that the use of the new rule significantly improves the effectiveness of ADT removal. We also show that our approach is competitive with respect to tools that extend CHC solvers with the use of inductive rules.

APA, Harvard, Vancouver, ISO, and other styles

46

K, Hari Govind V., Sharon Shoham, and Arie Gurfinkel. "Solving constrained Horn clauses modulo algebraic data types and recursive functions." Proceedings of the ACM on Programming Languages 6, POPL (January 16, 2022): 1–29. http://dx.doi.org/10.1145/3498722.

Full text

Abstract:

This work addresses the problem of verifying imperative programs that manipulate data structures, e.g., Rust programs. Data structures are usually modeled by Algebraic Data Types (ADTs) in verification conditions. Inductive invariants of such programs often require recursively defined functions (RDFs) to represent abstractions of data structures. From the logic perspective, this reduces to solving Constrained Horn Clauses (CHCs) modulo both ADT and RDF. The underlying logic with RDFs is undecidable. Thus, even verifying a candidate inductive invariant is undecidable. Similarly, IC3-based algorithms for solving CHCs lose their progress guarantee: they may not find counterexamples when the program is unsafe. We propose a novel IC3-inspired algorithm Racer for solving CHCs modulo ADT and RDF (i.e., automatically synthesizing inductive invariants, as opposed to only verifying them as is done in deductive verification). Racer ensures progress despite the undecidability of the underlying theory, and is guaranteed to terminate with a counterexample for unsafe programs. It works with a general class of RDFs over ADTs called catamorphisms. The key idea is to represent catamorphisms as both CHCs, via relationification , and RDFs, using novel abstractions . Encoding catamorphisms as CHCs allows learning inductive properties of catamorphisms, as well as preserving unsatisfiabilty of the original CHCs despite the use of RDF abstractions, whereas encoding catamorphisms as RDFs allows unfolding the recursive definition, and relying on it in solutions. Abstractions ensure that the underlying theory remains decidable. We implement our approach in Z3 and show that it works well in practice.

APA, Harvard, Vancouver, ISO, and other styles

47

Okada, Mitsuhiro. "Wittgenstein's Uniqueness Rule as an Elimination Rule of Inductive Types:." Kagaku tetsugaku 53, no. 2 (March 31, 2021): 95–114. http://dx.doi.org/10.4216/jpssj.53.2_95.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Cao, Qinxiang, and Xiwei Wu. "Countability of Inductive Types Formalized in the Object-Logic Level." Electronic Proceedings in Theoretical Computer Science 337 (July 16, 2021): 55–70. http://dx.doi.org/10.4204/eptcs.337.5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Naumann, David A. "A recursion theorem for predicate transformers on inductive data types." Information Processing Letters 50, no. 6 (June 1994): 329–36. http://dx.doi.org/10.1016/0020-0190(94)00049-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

ERWIG, MARTIN. "Inductive graphs and functional graph algorithms." Journal of Functional Programming 11, no. 5 (August 29, 2001): 467–92. http://dx.doi.org/10.1017/s0956796801004075.

Full text

Abstract:

We propose a new style of writing graph algorithms in functional languages which is based on an alternative view of graphs as inductively defined data types. We show how this graph model can be implemented efficiently, and then we demonstrate how graph algorithms can be succinctly given by recursive function definitions based on the inductive graph view. We also regard this as a contribution to the teaching of algorithms and data structures in functional languages since we can use the functional-style graph algorithms instead of the imperative algorithms that are dominant today.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!