Showing 1–5 of 5 results for author: Caruso, S

CNL2ASP: converting controlled natural language sentences into ASP

Authors: Simone Caruso, Carmine Dodaro, Marco Maratea, Marco Mochi, Francesco Riccio

Abstract: Answer Set Programming (ASP) is a popular declarative programming language for solving hard combinatorial problems. Although ASP has gained widespread acceptance in academic and industrial contexts, there are certain user groups who may find it more advantageous to employ a higher-level language that closely resembles natural language when specifying ASP programs. In this paper, we propose a novel… ▽ More Answer Set Programming (ASP) is a popular declarative programming language for solving hard combinatorial problems. Although ASP has gained widespread acceptance in academic and industrial contexts, there are certain user groups who may find it more advantageous to employ a higher-level language that closely resembles natural language when specifying ASP programs. In this paper, we propose a novel tool, called CNL2ASP, for translating English sentences expressed in a controlled natural language (CNL) form into ASP. In particular, we first provide a definition of the type of sentences allowed by our CNL and their translation as ASP rules, and then exemplify the usage of the CNL for the specification of both synthetic and real-world combinatorial problems. Finally, we report the results of an experimental analysis conducted on the real-world problems to compare the performance of automatically generated encodings with the ones written by ASP practitioners, showing that our tool can obtain satisfactory performance on these benchmarks. Under consideration in Theory and Practice of Logic Programming (TPLP). △ Less

Submitted 17 November, 2023; originally announced November 2023.

Comments: Under consideration in Theory and Practice of Logic Programming (TPLP)

On the genericity of pseudo-Anosov braids II: conjugations to rigid braids

Authors: Sandrine Caruso, Bert Wiest

Abstract: We prove that generic elements of braid groups are pseudo-Anosov, in the following sense: in the Cayley graph of the braid group with n $\ge$ 3 strands, with respect to Garside's generating set, we prove that the proportion of pseudo-Anosov braids in the ball of radius l tends to 1 exponentially quickly as l tends to infinity. Moreover, with a similar notion of genericity, we prove that for generi… ▽ More We prove that generic elements of braid groups are pseudo-Anosov, in the following sense: in the Cayley graph of the braid group with n $\ge$ 3 strands, with respect to Garside's generating set, we prove that the proportion of pseudo-Anosov braids in the ball of radius l tends to 1 exponentially quickly as l tends to infinity. Moreover, with a similar notion of genericity, we prove that for generic pairs of elements of the braid group, the conjugacy search problem can be solved in quadratic time. The idea behind both results is that generic braids can be conjugated "easily" into a rigid braid. △ Less

Submitted 26 September, 2013; v1 submitted 24 September, 2013; originally announced September 2013.

On the genericity of pseudo-Anosov braids I: rigid braids

Authors: Sandrine Caruso

Abstract: We prove that, in the $l$-ball of the Cayley graph of the braid group with $n \geqslant 3$ strands, the proportion of rigid pseudo-Anosov braids is bounded below independently of $l$ by a positive value. We prove that, in the $l$-ball of the Cayley graph of the braid group with $n \geqslant 3$ strands, the proportion of rigid pseudo-Anosov braids is bounded below independently of $l$ by a positive value. △ Less

Submitted 25 September, 2013; v1 submitted 17 June, 2013; originally announced June 2013.

MSC Class: 20F36; 20F65; 20F69; 05C50

A family of pseudo-Anosov braids whose super summit sets grow exponentially

Authors: Sandrine Caruso

Abstract: We prove that the size of the super summit set of a braid can grow exponentially with the canonical length of the braid, even for pseudo-Anosov braids. We prove that the size of the super summit set of a braid can grow exponentially with the canonical length of the braid, even for pseudo-Anosov braids. △ Less

Submitted 14 June, 2013; v1 submitted 23 February, 2013; originally announced February 2013.

Journal ref: Journal of Knot Theory and its Ramifications (2013), Vol. 22, No. 9

Combinatoire du point de croix

Authors: Xavier Caruso, Sandrine Caruso

Abstract: This paper deals with a popular form of counted-thread embroidery: the cross-stitch. More precisely, we are interested in the minimal length of embroidery thread one need to fill a given picture. We give a complete answer to this problem for 4-connexe pictures (the notion is defined in the paper). In a last part, we study several other examples. This paper deals with a popular form of counted-thread embroidery: the cross-stitch. More precisely, we are interested in the minimal length of embroidery thread one need to fill a given picture. We give a complete answer to this problem for 4-connexe pictures (the notion is defined in the paper). In a last part, we study several other examples. △ Less

Submitted 24 January, 2010; originally announced January 2010.

Comments: 20 pages

MSC Class: 05B99 ; 05C99