Pouyan Razmshoar

S Hajir Bahrami

Mohammad Rabiee

Marie Hangouet

Marie Martin

Abdelhamid Errachid

Nicole Jaffrezic-Renault

S Hajir Bahrami

A novel electrochemical immunosensor for ultrasensitive detection of tumor necrosis factor α based on polystyrene -PAMAM dendritic polymer blend nanofibers

Keywords: Electrospun nanofibers, Polystyrene (PS), Polyamidoamine (PAMAM), Electrochemical impedance spectroscopy (EIS), immunosensor, tumor necrosis factor-α (TNF-α)

A simple, rapid, and highly sensitive label-free immunosensor based on polystyrene (PS)-polyamidoamine (PAMAM) dendritic polymer nanofibers (NFs) for detection of tumor necrosis factor-α (TNF-α) cytokine was developed. The choice of PAMAM was due to the possibility of designing the surface of NFs to create a novel interface with the high control ability of the density of amine groups at the surface by which capture antibody (anti-TNF-α) could be covalently attached to the surface of NFs through glutaraldehyde (GA) coupling chemistry. Evaluation of the electrode surface using cyclic voltammetry (CV) proved the electrode manufacturing stages were successful by decreasing the peak current values due to the blockage of electron transfer by the biomolecule layer on the surface of NFs, as well as the ability to precisely control the current peak by changing the diameter of the NFs and the concentration of dendrimer. Electrochemical impedance spectroscopy (EIS) was used to test the detection capability of the immunosensors and compare the role of the amount of PAMAM presented on the surface of NFs on their analytical performance. Increasing the concentration of dendrimer greatly increased the sensitivity of immunosensors due to the higher stabilization of the antibody on the nanofiber surface. The immunosensor had a very high affinity for TNFα cytokines, with a linear response ranging from 10 to 200 pg/mL and a low limit of detection (LOD) of 669 fg/mL. Interference results with Interleukin-10 (IL-10) cytokine showed that the immunosensor was extremely specific and may be utilized to detect cytokines in clinical diagnosis.

Introduction

Tumor Necrosis Factor-alpha (TNF-α) is a pro-inflammatory cytokine produced by lymphocytes and macrophages that has been implicated in the stimulation of the acute phase response, anticancer activity, and immune system regulation [1,[START_REF] Bahk | A new concept for efficient sensitivity amplification of a QCM based immunosensor for TNF-α by using modified magnetic particles under applied magnetic field[END_REF]. According to recent researches, TNF-α levels in a patient's blood plasma and saliva are linked to heart failure (HF), and it can be used as a specific biomarker in detecting the first signs of future cardiovascular events [START_REF] Vozgirdaite | Development of an immunoFET for analysis of tumour necrosis factor-α in artificial saliva: Application for heart failure monitoring[END_REF][START_REF] Bahri | Capacitance electrochemical biosensor based on silicon nitride transducer for TNF-α cytokine detection in artificial human saliva: Heart failure (HF)[END_REF]. Since the concentration of TNF-α in healthy human serum is less than 10 pg/mL, and in the serum of patients with severe autoimmune diseases is between 10-300 pg/mL depending on the severity of the disease, accurate estimating its concentration in human fluids is a significant challenge and important to early diagnosis of disease [START_REF] Bahri | Capacitance electrochemical biosensor based on silicon nitride transducer for TNF-α cytokine detection in artificial human saliva: Heart failure (HF)[END_REF][START_REF] Yagati | Bioelectrochemistry Electrochemical immunosensor for highly sensitive and quantitative detection of tumor necrosis factor-α in human serum[END_REF]. Traditional methods such as ELISA for TNF-α detection have always disadvantages including long assay times, large sample volumes for analysis, the inability to assess in real time, and the necessity for a specialist. [START_REF] Sun | Biosensors and Bioelectronics Sensitive immunosensor for tumor necrosis factor a based on dual signal amplification of ferrocene modified self-assembled peptide nanowire and glucose oxidase functionalized gold nanorod[END_REF][START_REF] Sánchez-Tirado | Electrochemical immunosensor for simultaneous determination of interleukin-1 beta and tumor necrosis factor alpha in serum and saliva using dual screen printed electrodes modified with functionalized double-walled carbon nanotubes[END_REF]. Electrochemical immunosensors have received much interest in recent years as an alternative to conventional approaches in TNF-α detection because of their high sensitivity, easy instrumentation, accuracy, and quick response [START_REF] Qi | Decoration of Reduced Graphene Oxide Nanosheets with Aryldiazonium Salts and Gold Nanoparticles toward a Label-Free Amperometric Immunosensor for Detecting Cytokine Tumor Necrosis Factor-α in Live Cells[END_REF][START_REF] Barhoumi | A novel chronoamperometric immunosensor for rapid detection of TNF-Α in human saliva[END_REF][START_REF] Yin | Biosensors and Bioelectronics Electrochemical immunosensor of tumor necrosis factor ␣ based on alkaline phosphatase functionalized nanospheres[END_REF].

In this work, based on two novel perspectives a highly sensitive electrochemical immunosensor for TNF-α cytokine detection was developed. First, the usage of the NFs structure in immunosensor construction with the goal of providing a diagnostic platform with a large surface area to immobilize TNF-α antibodies in such a way that they have maximal TNF-α cytokine accessibility to improve immunosensor sensitivity. The use of NFs in the production of electrochemical immunosensors might lead to the development of a new generation of miniaturized immunosensors that can answer key issues of previous works such as increased sensitivity, simplicity, and rapid detection. Second, fiber surface engineering in terms of the kind and quantity of functional groups suited for covalent immobilization of TNF-α antibody with a specific distance to build a protein-friendly interface with high stability so that the analyte may be detected in the smallest amount feasible. PAMAM dendrimers are globular, highly branched polymeric macromolecules with a polyvalent core (ethylene diamine (EDA)), internal repeating branched units (amidoamine), and high terminal active surface groups [START_REF] Bahadir | Poly(amidoamine) (PAMAM): An emerging material for electrochemical bio(sensing) applications[END_REF][START_REF] Hasanzadeh | Dendrimerencapsulated and cored metal nanoparticles for electrochemical nanobiosensing[END_REF]. Dendrimers provide the possibility of immobilizing bioreceptors for the design of immunosensors due to their unique structural and chemical features, such as multiple functional groups, hydrophilicity, high mechanical and chemical stability, and similar size to biomolecules [START_REF] Elancheziyan | Viologen-terminated polyamidoamine (PAMAM) dendrimer encapsulated with gold nanoparticles for nonenzymatic determination of hydrogen peroxide[END_REF][START_REF] Chandra | Fabrication of a label-free electrochemical immunosensor using a redox active ferrocenyl dendrimer[END_REF]. Accordingly, great emphasis has been placed on the use of PAMAM in the production of extremely sensitive electrochemical immunosensors in order to speed up the electron transfer process, enhance antibody immobilization efficiency, and improve electrochemical responses and signal amplification [START_REF] Liu | A sensitive electrochemical immunosensor based on PAMAM dendrimer-encapsulated Au for detection of norfloxacin in animal-derived foods[END_REF][START_REF] Liu | An electrochemiluminescence immunosensor for thyroid stimulating hormone based on polyamidoamine-norfloxacin functionalized Pd-Au core-shell hexoctahedrons as signal enhancers[END_REF][START_REF] Razzino | An electrochemical immunosensor using gold nanoparticles-PAMAM-nanostructured screen-printed carbon electrodes for tau protein determination in plasma and brain tissues from Alzheimer patients[END_REF]. A previous study on the modification of the ELISA kit surface using PAMAM for TNF-α cytokine detection showed increased sensitivity and the detection limit through better orientation of the antibodies compared to the commercially ELISA kit [START_REF] Bosnjakovic | A dendrimer-based immunosensor for improved capture and detection of tumor necrosis factor-α cytokine[END_REF]. In this work, PS-PAMAM dendritic polymer NFs were produced for the first time, with doped PS and PAMAM dendritic polymer with different concentrations, then allowing covalent interaction with the Fc region of the TNF antibody after amine group activation. As a result, the impact of increasing PAMAM concentration on its presence on the fiber surface and TNF-α detection was investigated. Electrochemical impedance was utilized in the final step to detect changes in electron transport properties after the development of antibody-antigen immune complexes on the surface of NFs mats deposited on a gold electrode. The immunosensors' repeatability, reproducibility, and selectivity were all examined.

Materials and methods

Chemicals and Reagents

In the supplementary information, the reagents, instruments, and characterizations parts were described in detail.

PS and PS-PAMAM nanofibrous mats preparation

PS granules were dissolved in N,N,-dimethylformamide (DMF) solvent at room temperature (RT) under magnetic stirring overnight to prepare a 20 wt. % PS solution for electrospinning. The preparation of PS-PAMAM NFs mats with different mass ratios of 85-15, 75-25, and 65-35 was conducted in two step process.

The precise quantities of PS and PAMAM dendritic polymer were dissolved separately in DMF solvent for each mass ratio. The overnight stirring was conducted at RT to obtain clear solutions. The PAMAM dendritic polymer solution was gently added to the PS solution in the second step, and the mixture was stirred for 4 h to obtain a PS-PAMAM 20 wt. % solution. After this step, PS-PAMAM solutions with different mass ratios were used immediately for electrospinning. The solutions were loaded into a 1ml syringe supplied with a laser-cut needle (22 gages) and fed through a polytetrafluoroethylene (PTFE) tube from the syringe to the nozzle using the syringe pump (electrospinning instrument, Spraybase®, Ireland).

In order to obtain NFs with a bead-less morphology with uniformity in diameter, various parameters such as voltage, injection rate and distance from the nozzle to the collector were changed. The electrospinning parameters were 27 kV for the applied voltage, rate 0.25 ml/h and the tip-to-collector distance 20 cm.

After obtaining uniform and bead-less NFs, they were electrospun on the surface of gold electrode that was placed on a collector for 1min. Before electrospinning, the gold electrodes were placed in acetone for 15min and then in ethanol in an ultrasonic bath for 15min for cleaning. At each stage and at the end, the surface of the gold electrodes was rinsed thoroughly with ultrapure water. They were dried with a gentle stream of nitrogen and then placed in an UV/ozone ProCleanerTM for 30min to eliminate any possible organic contamination.

GA-PS and GA-PS-PAMAM nanofibrous mats preparation

GA coupling agent was used to activate PAMAM dendritic polymer amine groups on the surface of NFs to allow covalent bonding with amino groups in the Fc region of anti-TNF-α. Briefly, gold electrodes containing PS and PS-PAMAM NFs were exposed to saturated GA vapors in the desiccator for 2h.

Antibodies and Antigens standard solutions preparation

The anti-TNF-α and AgTNF-α have been reconstituted in PBS buffer (10 mM, pH 7.4) and then aliquoted at 20 µL according to the protocol provided by the supplier to get a stock solution with a final concentration of 500 μg/mL and 100 μg/mL, respectively. The aliquots were stored at -20°C until use. The anti-TNF-α solution was diluted at 10 μg/mL in PBS (10 mM, pH 7.4). The standard solutions containing of AgTNF-α were prepared at five different concentrations (10, 25, 50,100, and 200 pg/mL) by dissolving the appropriate amount of the stock solution in PBS (10 mM, pH 7.4) and stored at 4°C. All the standard solutions were prepared by weighing.

immunosensor preparation

Immunosensor construction was done by pipetting 50 μl of anti-TNF-α (10 µg/mL) on the surface of NFs and then incubating for 1h at 4°C. After this step, the electrode surface was gently washed three times with PBS (10 mM, pH 7.4) to eliminate unbound antibodies from the NFs 's surface. Finally, blocking treatment for reducing non-specific binding and blocking remaining active sites was done by pipetting 100 μl of BSA 1% solution on the NFs and incubating for 1h at 4°C.

Electrochemical measurements

For the detection of AgTNF-α, the NFs modified gold electrode was subjected to successive immobilization with standard solutions (50μl) containing different concentrations of AgTNF-α prepared as described in the section 2.4 for 30min at RT (20 ± 1°C) in the electrochemical cell, followed by PBS washing to remove unbounded AgTNF-α cytokine. At each AgTNF-α concentration, an EIS response was then recorded by filling the cell with 5ml of 5mM of K3Fe(CN)6/K4Fe(CN)6 in PBS buffer at pH 7.4. After each EIS measurement, the electrolyte solution in the cell was removed and the cell were washed with PBS solution to remove all adsorbed electrolyte solution from surface of NFs and prevent denaturation of anti-TNF-α.

Results and discussion

Characterization of nanofibrous mats

FTIR Spectroscopy

The ATR-FTIR spectra of PS and PS-PAMAM NFs with different concentrations are presented in Fig. 1.

The bands at 3080-3024, 2920, and 2846 cm -1 associated with the aromatic C-H stretching vibration absorption and the existence of CH2, respectively were found in the spectrum of pure PS NFs. Also, the peaks at 1939, 1869, 1801, and 1741 cm -1 were representative to overtone aromatic. The C=C stretching vibration absorption were seen at 1600 cm -1 and bending vibrations of CH2 were observed at 1492, and 1451 cm -1 . The absorption peaks at 755 and 696 cm -1 associated with C-H out-of-plane bending vibration absorption were also seen. In comparison to pure PS, the amine and amide peaks of PAMAM emerged in the spectra of NFs containing dendrimer. The spectrum of PS-PAMAM NFs with different mass ratio along with characteristic PS peaks exhibited a new peak at 3268 cm -1 correspond to N-H stretching vibration. The C=O of amide I band, N-H bending and C-N stretch of amide II band, and C-N stretch of amide III bands appeared at peaks of 1645, 1551, and 1372 cm -1 , respectively. In addition, the peaks at 1155 and 1122 cm - 1 that belong to the C-N stretch of amine were found. The peak at 2810 cm -1 due to the stretching bands of C-H close to NH group was observed. The intensity of the mentioned peaks increases as dendrimer concentrations increase, confirming the existence of more dendrimer on the PS-PAMAM NFs surface.

Morphological Studies

In order to evaluate NFs in terms of diameter, uniformity, and the effect of PAMAM dendritic polymer on PS morphology, FE-SEM micrographs were prepared. Fig. 2a andb demonstrate FE-SEM micrographs of PS NFs at two magnifications, with the average diameter of 985±303 nm. Fig. 2c andd show micrographs of PS-PAMAM NFs (65-35), which have significantly reduced fiber diameters compared to pure PS. This decrease in diameter is due to a decrease in solution viscosity, increasing the conductivity of electrospinning solution and surface charge density of ejected jet with increasing dendrimer ratio due to low molecular weight and the cationic characteristic of PAMAM dendritic polymer, respectively, whereby the polymer jet is subjected to more elongation force in a constant electric field. This increase in elongation is also evident in the morphology of the NFs so that the porosity of the PS nanofiber surface was disappeared and the surface became smoother. Table 1 shows the results of the electrical conductivity of electrospinning solutions. According to the results, the electrical conductivity of the PS solution was 0.4 μS/cm, while it reached 24.0 μS/cm in the sample 65-35. The diameter of PS-PAMAM NFs with ratios of 85-15, 75-25, and 65-35 were 350±126 nm, 319±86 nm, and 295±94 nm, respectively. Significant results can be summarized based on the morphology of the resulting NFs. (1) Modification with PAMAM has substantially decreased the diameter and increased the accessible surface area of the resultant NFs compared to pure PS, allowing more anti-TNF-α to be immobilized on the surface and increasing the immunosensor's sensitivity. [START_REF] Bahk | A new concept for efficient sensitivity amplification of a QCM based immunosensor for TNF-α by using modified magnetic particles under applied magnetic field[END_REF] The uniformity of the diameter, whether in a single fiber or in the average diameter of the fibers, as well as the bead-less morphology, contribute to immunosensor reproducibility. (3) The porous structure of the NFs mats allows the desired analyte to access even the immobilized bioreceptor in the lower layers of the fibers, and provides no penetration resistance. (4) The morphology of PS NFs has not changed after doping with PAMAM dendritic polymer, which is a benefit for the creation of reproducible immunosensors.

Water contact angle

The images of the water droplets on the pure PS and PS-PAMAM NFs (65-35) on the surface of the gold electrode are inserted in Fig. 2. Pure PS NFs showed a contact angle of 147.2±1.1°, which is due to the lack of functional groups in their structure and their hydrophobic nature. The contact angles of samples 85-15, 75-25, and 65-35, have been greatly reduced to 48.2±1.2°, 31.8±1.3°, and 15.4±1.2°, respectively.

According to the results, the presence of PAMAM in the structure of NFs on the one hand reduces the diameter of fibers and increases their surface area and, on the other hand, increases more hydrophilic amine groups on the surface of PS NFs, both of which play an effective role in NFs surface properties. As a result of the high hydrophobicity of PS and absence of functional groups on its surface, there is a lack of homogeneous distribution of anti-TNF-α on the fiber surface, as well as covalent bonding with the NFs' surface. In PS-PAMAM samples, increasing the concentration of the PAMAM provides increased hydrophilicity and higher functional groups to the anti-TNF-α on a more uniform immobilization at the fiber surface. Regardless of the chemical structure and morphology of NFs and only based on the shape of the water droplet on the NFs surface in Fig. 2, unlike the PS sample, the droplet in the PS-PAMAM (65-35) spread well on the surface. While the procedures of immobilizing anti-TNF-α on the surface of the fibers were accomplished by pipetting a specific quantity of antibody onto the fibers' surface, the hydrophilic properties of PS-PAMAM fibers allow for more uniform antibody immobilization. However, immobilization of anti-TNF-α on the surface of PS NFs confined to the droplet's position. To examine the surface properties of NFs following treatment with GA and anti-TNF-α immobilization, the contact angle of the NFs was measured (Table 1). The contact angle increased after applying PS-PAMAM NFs with GA owing to the interaction of dendrimers amine groups on the surface of NFs with GA and the formation of Schiff bases. The contact angle of sample 65-35 rose from 15.4±1.2° to 35.9±4.7°after treatment with GA, indicating that GA forms covalent bonds with amine groups. However, the contact angle of PS NFs did not change after GA treatment due to the lack of amine groups at their surface. The contact angle fell to 16.4±2.5° after immobilization of anti-TNF-α on sample 65-35, indicating that antibodies were immobilized at the fiber surface. This trend has been true for samples 85-15 and 75-25. The slight decrease in the contact angle observed in the PS sample is related to the grafting of the anti-TNF-α on the surface of the NFs.

Immunodetection and Interference of TNF-α cytokines

The Cyclic voltammograms (CVs) were performed in 10 mM PBS (pH 7.4) with 5.0 mM [Fe(CN)6] 3-/4-as the redox probe from -0.2 to +0.6 V and the scan rate of 60 mV/s to provide more specific information about electrodes containing NFs and to analyze electrode behavior changes throughout stepwise immunosensor fabrication. As shown in Fig. 3a, the PS-PAMAM NFs with different concentrations exhibit a couple of reversible redox peaks. As the concentration of PAMAM increases, the peak current increases, which is related to the increase in effective surface area with decreasing fiber diameter as well as the effect of dendrimer on electron transfer. The disappearance of the oxidation and reduction peaks of the redox couple in the pure PS NFs is related to their non-conducting properties, large diameter, and high hydrophobicity. How PAMAM improves electron transfer in NFs is better understood by imagining a network of it within a 3D nanofiber and on its surface that some of them face the working electrode and the others facing the solution. This indicates that from a certain concentration onwards the amount of PAMAM reaches a critical level to form a network within the NFs and on their surface, which increases the electron transfer. This network is well-formed in sample 75-25, and with increased dendrimer concentration and decreasing fiber diameter (sample 65-35), more PAMAM will be present on the surface of the fibers, resulting in enhanced electron transport. Surface modification of the glassy carbon electrode with PAMAM produced similar outcomes in terms of increased electric flux, improved conductive capacity, noise reduction, and faster electron transfer processes on the electrode's surface [START_REF] Zhang | Redox and catalysis "all-in-one" infinite coordination polymer for electrochemical immunosensor of tumor markers[END_REF].

The redox current of [Fe(CN)6] 3-/4-after electrospinning of NFs (65-35) on the electrode surface (129.3 μA) has increased compared to the bare gold electrode (116.7 μA) due to the increase in high specific surface area and improved charge-transport by the PAMAM (Fig. 3b). After the immobilization of the anti-TNF-α and blocking with BSA, the redox current (111.2 μA) has decreased due to the formation of a layer of protein molecules on the surface of the fibers that insulate the electrode and prevent electron transmission between electrode and electrolyte. This confirms the ability of the substrate to immobilize anti-TNF-α.

Antibody activity on the surface of NFs was assessed by incubating 50 μl AgTNF-α (10 pg/mL) on the electrode surface for 30 min. The decrease in redox current (102.7 μA) and increase in peak-to-peak separation in voltammogram confirm the immunosensor is highly sensitive to TNF-α cytokine through the formation of immune complexes that could hinder electron transfer between the electrode and the electrolyte as insulating biomolecules.

Electrodes containing sample 65-35 NFs with 4 different deposition durations of 1, 2, 3, and 5 min were studied using SEM and CV to discover the ideal electrospinning time and to evaluate the influence of deposit time on the redox current of [Fe(CN)6] 3-/4-. Increasing the electrospinning duration induces more NFs to deposit, resulting in a thicker layer mat, as seen in Fig. S 1 (SI). The remarkable point in the images is the uniform diameter and the beaded-free structure of the NFs mats in different samples. This reaffirms the developed immunosensor is reproducible. The CV results show a decreasing trend in redox current with increasing electrospinning time (Fig. S 2). It is related to increasing the thickness of the NFs mats and decreasing the porosity between the NFs, which prevents penetration of [Fe(CN)6] 3-/4-to the electrode surface. The 1 min electrospinning was selected as the ideal time due to the following reasons. (1) having the highest current intensity in comparison to others, (2) supplying the appropriate and adequate quantity of NFs on the electrode surface, and (3) having the best adherence to the electrode surface and suitable stability throughout immobilization, blocking, and washing processes. Despite the role of the PAMAM in the good adhesion of NFs to the electrode surface, increasing the electrospinning duration leads the NFs to be attached only with their bottom layer and not in touch with the electrode surface. As a result, 1 min of electrospinning was chosen as the optimal time, and all immunosensors were made using this time.

The EIS was utilized to quantitatively analyze the performance and sensitivity of the developed immunosensor in detecting TNF-α cytokine and confirming the formation of immune complexes between anti-TNF-α and AgTNF-α on the NFs surface. The acquired Nyquist impedance plots for developed immunosensors are shown in Fig. 4, where the charge transfer resistance at the electrode surface (Rct) is proportional to the semi-circle diameter. The first semi-circle relates to anti-TNF-α immobilization on the surface of NFs at 4 °C for 1h. After this step, the immunosensors were evaluated to detect AgTNF-α in the concentration range of 10-200 pg/ml. The Nyquist plot of an immunosensor based on pure PS NFs is shown in Fig. 4a. Because of the lack of functional groups on the surface of pure PS NFs, it is not feasible to immobilize antibodies uniformly and covalently on these NFs. Only the anti-TNF-α was physically attached to the NFs' surface, leading to antibody accumulation, denaturation, and desorption at different sensing Table S1 compares the prepared immunosensor to previously reported literature in detail. The immunosensor has a wide linear detection range with the lowest LOD than previous electrochemical TNFα cytokine immunosensors. This is rooted in the high surface-to-volume ratio of NFs and allows antibodies to be covalently immobilized with a significantly higher density on the fiber surface, a high accessibility due to the porous structure. The electrospun NFs-based immunosensor produced in this study provided a flexible interface with a low-cost and simple production method, allowing the development of a new generation of immunosensors for insertion in a point of care testing.

The selectivity of the PS-PAMAM NFs-based immunosensor was also considered as a significant property of immunosensors. For this, all of the procedures used for AgTNF-α were repeated for cytokines IL-10 (Fig. 4f). According to the results, the developed immunosensor had higher selectivity and sensitivity to AgTNF-α compared to IL-10.

Conclusion

Nanostructured transducers along with the ideal surface chemistry design can lead to the development of highly sensitive immunosensors. In this work, a PS-PAMAM NFs-based immunosensor was developed that provided the ideal protein-friendly platform with a high surface area and a well-designed receptor surface for the immobilization of anti-TNF-α. The role of PAMAM dendritic polymer and its presence on the fiber surface at three different concentrations were investigated and sample 65-35 had the highest sensitivity and linear response for AgTNF-α due to the higher presence of dendrimer on the surface. This highly sensitive immunosensor, along with the easy and fast preparation method, provided conditions for the anti-TNF-α to be covalently immobilized on the fiber surface without losing their activity to detect the AgTNF-α with high sensitivity. This could be promising for the development of a point of care and flexible immunosensor with maximum analyte detection ability.

  stages. The immunosensor did not work and the semi-circles did not increase due to a low amount of immobilized anti-TNF-α and saturation of them on the surface of PS NFs. The Nyquist plots of PS-PAMAM NFs with different mass ratios 85-15, 75-25, and 65-35 are shown in Figures4b-d. The semi-circles gradually increased with increasing the AgTNF-α content in all PS-PAMAM NFs samples, indicating AgTNF-α biorecognition with anti-TNF-α on the surface of NFs. By comparing the semi-circle and linear part of the impedance spectra of the immunosensors, a smaller semi-circle with better diffusion of [Fe(CN)6] 3-/4-toward the surface of the electrode is observed with increasing PAMAM dendritic polymer concentration. This is due to decreased diameter and increased hydrophilicity, and the presence of PAMAM on the NFs surface, which enhances charge transfer for [Fe(CN)6] 3-/4-. This is in line with the findings of the CV of NFs with different PAMAM concentrations. After each step, the electrochemical parameters were calculated by fitting the Nyquist plot with Randles equivalent circuit, which provided the best fit for the impedance parameters (Fig.4inset). It consists of electrolyte resistance (Rs) in series with a parallel combination of constant phase element QCPE and charge transfer resistance (Rct). The calibration curve of developed immunosensors was drawn based on (R(antibodies)-R(antigens))/R(antibodies) obtained from the equivalent circuit against the logarithmic value of the AgTNF-α concentration (Fig.4e). The calibration graph of PS-PAMAM NFs-based immunosensors showed a linear correlation in ranges between 10 -200 pg/mL.Increasing the concentration of PAMAM has increased the slope of the graph and the higher detection sensitivity of the immunosensor due to the higher loading of antibodies on the surface of NFs. In comparison to the other samples, PS-PAMAM with the concentration of 65-35 has the highest slope, with a linear regression equation of ΔR/R = 0.379 ln [AgTNF-α]-0.461 and a correlation coefficient of R 2 = 0.987, indicating that this immunosensor has a higher sensitivity to antigen changes due to the higher presence of PAMAM and immobilization of antibodies on the surface of NFs. The LOD of immunosensor was 669 fg/mL based on 3 .S/m, where S is the residual standard deviation and m is the slope of the regression line. The trend is similar in samples 85-15 and 75-25, but they have a lower slope than samples 65-35: ΔR/R = 0.210 ln [AgTNF-α]-0.132 for sample 85-15 and ΔR/R = 0.2680 ln [AgTNF-α]-0.235 for sample 75-25. Table S1 compares the detection range and LOD of the developed immunosensor to those of previous electrochemical TNF-α immunosensors.

Fig. 1 .

 1 Fig. 1. ATR-FTIR spectra of (a) pure PS, (b) PS-PAMAM-(85-15), (c) PS-PAMAM-(75-25), and (d) PS-PAMAM-(65-35) NFs.

Fig. 2 .

 2 Fig. 2. FE-SEM images of (a) and (b) pure PS, (c) and (d) PS-PAMAM-(65-35) NFs, and (e) diameter distribution histograms of NFs. Insets in Fig.2 are the images of water droplets on the surface of electrospun NFs on a gold electrode.

Fig. 3 .

 3 Fig. 3. CVs of (a) pure PS and PS-PAMAM NFs with different concentrations, (b) bare gold, gold electrode containing PS-PAMAM-(65-35) NFs, anti-TNF-α -GA-PS-PAMAM-(65-35) NFs, and AgTNF-α -anti-TNF-α-GA-PS-PAMAM-(65-35) in a 10 mM PBS (pH 7.2) containing 5.0 mM [Fe(CN)6] 3-/4-(scan rate = 60 mV/s).

Fig. 4 .

 4 Fig. 4. Nyquist plots of impedance spectra obtained in 10 mM PBS (pH 7.4) solution containing 5mM [Fe(CN)6] 3-/4-for gold electrodes containing (a) pure PS, (b) PS-PAMAM-(85-15), (c) PS-PAMAM-(75-25), and (d) PS-PAMAM-(65-35) NFs for AgTNF-α detection ranging from 10-200 pg/mL. EIS: polarization potential of 0.2 V vs Ref, 1 Hz-100 kHz frequency range, and a sinus amplitude of 10 mV. Inset was the equivalent circuit model used to fit the impedance data. (e) calibration curves of the developed immunosensors for the detection of AgTNF-α cytokine. (f) Selectivity histograms of the developed immunosensors for the detection of Ag-TNF-α and IL-10 cytokine.

Acknowledgements P.R. thanks the Ministry of Science, Research and Technology of the Islamic Republic of Iran for providing the scholarship. The authors acknowledge the financial support of the European Union's Horizon 2020 research and innovation programme, Project NMBP-13-2017 KardiaTool (Grant agreement No.768686) and POC4Allergies (Ref.ERAPERMED2019-127).

Graphical abstract


Philippe Balbiani
email: philippe.balbiani@irit.fr

Valentin Goranko

Guido Sciavicco

Two-sorted Point-Interval Temporal Logics

Keywords: point and interval temporal logics, decidability, complexity

There are two natural and well-studied approaches to temporal ontology and reasoning: point-based and interval-based. Usually, interval-based temporal reasoning deals with points as particular, duration-less intervals. Here we develop explicitly two-sorted point-interval temporal logical framework whereby time instants (points) and time periods (intervals) are considered on a par, and the perspective can shift between them within the formal discourse. We focus on fragments involving only modal operators that correspond to the inter-sort relations between points and intervals. We analyze their expressiveness, comparative to interval-based logics, and the complexity of their satisfiability problems. In particular, we identify some previously not studied and potentially interesting interval logics.

Introduction

The predominant approach in the studies of temporal reasoning and logics has been based on the assumption of time points (instants) as the primary temporal on-tological entities. However, there have also been active studies of interval-based temporal reasoning and logics over the past 2 decades, starting with the seminal work of Halpern and Shoham [START_REF] Halpern | A propositional modal logic of time intervals[END_REF] introducing the multi-modal logic, that we will call HS, comprising modal operators for all possible relations (known as Allen's relations [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF]) between two intervals in a linear order, and followed by a series of publications studying expressiveness and decidability/undecidability and complexity of the fragments of HS, e.g., [START_REF] Goranko | A road map of interval temporal logics and duration calculi[END_REF][START_REF] Bresolin | Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions[END_REF]. For a detailed philosophical study of both approaches -point-based and interval-based -see [START_REF] Van Benthem | The Logic of Time (2nd Edition)[END_REF]. Many studies on interval logics have considered the so-called 'non-strict' interval semantics, allowing point-intervals (with coinciding endpoints) along with proper ones, and thus encompassing the instant-based approach, too; see e.g., [START_REF] Halpern | A propositional modal logic of time intervals[END_REF][START_REF] Goranko | A road map of interval temporal logics and duration calculi[END_REF][START_REF] Bresolin | Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions[END_REF]]. Yet, little has been done so far on formal treatment of both temporal primitives, points and intervals, on a par, in a common, two-sorted framework. The present paper purports to provide a systematic such treatment. Our work is motivated by several observations:

• Natural languages incorporate both ontologies on a par, without assuming the primacy of one over the other, and have the capacity to shift smoothly the perspective from instants to intervals and vice versa within the same discourse.

• There are various temporal scenarios which neither of the two ontologies alone can grasp properly. In particular, sometimes neither the treatment of intervals as sets of their internal points, nor the treatment of points as 'instantaneous' intervals, is really adequate. For example, a sentence like 'Ever since he met her for the first time, he could not stop thinking about her and kept calling her several times every night until she would give him a brush-off, and then after being silent for a while he would phone again...' cannot be properly represented in either instant-only or interval-only framework. As another example, consider a typical safety requirement of an intelligent systems that controls a rail crossing:'At the exact moment in which the train passes over the sensor, the rail crossing bar starts to close; the bar will start to open again a while after the train passes over the second sensor'.

• The technical identification of intervals with sets of their internal points, or of points as instantaneous intervals leads also to conceptual problems, e.g. of confusing events and fluents. Instantaneous events are represented by time intervals and should be distinguished from instantaneous holding of fluents, which are evaluated at time points. Formally, the point a should be distinguished from the interval [a, a] and the truths in these should not necessarily imply each other.

• Moreover, the area of artificial intelligence is concerned with purely practical problems related to the formal representation and reasoning of intelligent agents on various temporal and spatial aspects such as position, motion, actions, processes, events, fluents, etc. Some of these can be adequately represented in either of the rival ontologies, while others become awkward, if not meaningless, in one or the other of them.

• Finally, we note that, while differences in the expressiveness have been found

between the strict and non-strict semantics for some interval logics (see [START_REF] Della Monica | Expressiveness of the Interval Logics of Allens Relations on the Class of all Linear Orders: Complete Classification[END_REF], for example), so far no distinction in the decidability of the satisfiability has been found. Therefore, we believe that an attempt to systemize the role of points, intervals, and their interaction, would make good sense not only from a purely ontological point of view, but also from algorithmic and computational perspectives.

There have been several logical studies of the relationship between instants and intervals, including [START_REF] Hamblin | Instants and intervals[END_REF][START_REF] Van Benthem | The Logic of Time (2nd Edition)[END_REF][START_REF] Roeper | Intervals and tenses[END_REF]. One of the conceptual precursors of our present study is [START_REF] Galton | The Logic of Aspects[END_REF] where Galton introduces a two-sorted 'aspectual calculus' involving points and events on a par. Further, in [START_REF] Galton | A critical examination of Allen's theory of action and time[END_REF] Galton argues that Allen's interval-based theory of time and action is inadequate for representing continuous change and advocates the necessity of adding time instants in their own capacity to it. Other explicit two-sorted point-interval formal studies of time of which we are aware include the system IP from [START_REF] Vila | IP: An instant-period based theory of time[END_REF][START_REF] Schwalb | Temporal constraints: A survey[END_REF], based on the first-order theory of point-interval structures, and the system LNint from [START_REF] De Guzman | Lnint: A temporal logic that combines points and intervals and the absolute and relative approaches[END_REF], where, however, the interval type plays a secondary role since formulae are always evaluated at points, and the time line is assumed to be discrete (the set of integers).

Here we develop explicitly two-sorted modal approach to the point-interval temporal reasoning whereby time instants (points) and time periods (intervals) are considered on a par, and the perspective can shift between them within the formal discourse. We compare that language with those interval logics with non-strict semantics, that we already know to be right on the border between decidable and undecidable. One of the most important examples on the decidable side is that of Propositional Neighborhood Logic (PNL) with non-strict semantics [START_REF] Bresolin | Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions[END_REF], that corresponds to the fragment of HS with the modal operator for meets and met-by only, plus the modal constant π for point-interval; In [START_REF] Montanari | Maximal decidable fragments of Halpern and Shoham's modal logic of intervals[END_REF] it has been shown that PNL is almost maximal (amongst the fragments of HS) w.r.t. decidability on the class of all linear orders, while the pair of operators corresponding to Allen's relations ends and ended by constitutes the most interesting exception, as they can be added to PNL without losing the decidability when interpreted over finite models or models based on the set of natural numbers N. Here, we first introduce the logic PI comprising modal operators for all possible binary relations between points and intervals. It is easy to see that PI is at l east as expressive as HS, and therefore it is undecidable under the same assumptions where the latter is. Then, we focus on the fragment PI mix involving only the modal operators that correspond to the inter-sort relations between points and intervals. We analyze the expressiveness and the complexity of the satisfiability problem of PI mix and some of its fragments. In particular, we identify some previously not studied, in the context of fragments of HS, and potentially interesting interval logics whose decidability/undecidability status can be deduced from already known results for fragments of HS and at least one of them has an unexpectedly low complexity.

Preliminaries: the Logic HS

In the classical interval setting, given a linearly ordered set D = D, < , an interval (also called non-strict interval) is defined as a pair [a, b], where a, b ∈ D and a ≤ b. The logic HS, introduced in [START_REF] Halpern | A propositional modal logic of time intervals[END_REF], is defined over a set of propositional letters AP, denoted by p, q, . . ., by using the classical propositional operators ¬, ∨ (whereas the remaining ones can be considered as shortcuts), and a modal operator for each of the 12 Allen's relation, that is, each possible binary relation between two intervals on linear orders (excluding equality, the modal operator for which is trivial). The standard notation for such modal operators is as follows: A (in the non-strict semantics, it is usually denoted by 3 r ) for the relation meets, B for begins, E for ends; moreover and, for each X ∈ { A , B , E }, X denotes its inverse (in the non-strict semantics, 3 l denotes the inverse of 3 r ), and the modal operators for the remaining six operators can easily be defined in terms of the above ones. In this setting, a HS-model M is defined as M = D, I(D) + , V , where I(D) + is the set of all non-strict intervals over D, and V : I(D) + → 2 AP is a labeling function. The semantics of HS-formulae ϕ is as follows:

• M, [a, b] p iff p ∈ V([a, b]); • M, [a, b] π iff a = b; • M, [a, b] A ψ (resp., 3 r ψ) iff there exists c > b (resp., c ≥ b) such that M, [b, c] ψ; • M, [a, b] B ψ iff there exists a ≤ c < b such that M, [a, c] ψ; • M, [a, b] E ψ iff there exists a < c ≤ b such that M, [c, b] ψ; • M, [a, b] D ψ iff there exist a < c < d < b such that M, [c, d] ψ; • M, [a, b] O ψ iff there exist a < c ≤ b < d such that M, [c, d] ψ; • M, [a, b] L ψ iff there exist a < b < c ≤ d such that M, [c, d] ψ.
where the semantics of classical operators is as standard. The semantics of the inverse operators can be easily deduced from the above clauses; for example, we have:

• M, [a, b] A ψ (resp., 3 l ψ) iff there exists c < b (resp., c ≤ b) such that M, [c, b] ψ; • M, [a, b] B ψ iff there exists c > b such that M, [a, c] ψ; • M, [a, b] E ψ iff there exists c < a such that M, [c, a] ψ.
With every subset { X 1 , . . . , X k } of HS modal operators, we associate the fragment X 1 X 2 . . . X k of the logic HS that features all and only those modal operators, possibly extended with the modal constant π, denoted in this case by X 1 X 2 . . . X k π , if π is not definable in that particular fragment. In the recent literature, PNL (resp., PNL π ) is also used to denote the fragment AA (resp., 3 r 3 π l ). Recent results concerning decidability, undecidability, and expressive power of fragments of HS include [START_REF] Della Monica | Expressiveness of the Interval Logics of Allens Relations on the Class of all Linear Orders: Complete Classification[END_REF][START_REF] Montanari | Maximal decidable fragments of Halpern and Shoham's modal logic of intervals[END_REF][START_REF] Bresolin | Decidable and Undecidable Fragments of Halpern and Shoham's Interval Temporal Logic: Towards a Complete Classification[END_REF].

In [START_REF] Halpern | A propositional modal logic of time intervals[END_REF], the satisfiability problem for the logic HS has been proved to be undecidable over all interesting classes of linearly ordered sets. In the classification of decidability/undecidability for most of the interesting fragments of HS for both the strict and non-strict semantics (i.e., classes of models that exclude, resp., include point-intervals), the case of PNL/PNL π , is probably the most interesting one on the decidable side. Its satisfiability problem is decidable in finite, discrete, and dense case, as well as in the class of all linearly ordered sets, among others; in all these cases, it is NEXPTIME-complete . More recently, the fragment AAEE has been shown to be decidable in the finite case and over the set of natural numbers [START_REF] Montanari | Maximal decidable fragments of Halpern and Shoham's modal logic of intervals[END_REF], but its complexity is non-elementary. EXPSPACE-completeness holds, among others, for the fragment ABB in the same cases as PNL/PNL π (see [START_REF] Bresolin | What's decidable about Halpern and Shoham's interval logic? the maximal fragment abbl[END_REF] for a complete survey of these decidable fragments). Finally, in the view of our classification of the expressive power of some of the languages that we introduce in the following sections, we also note that the fragment AAD (and, therefore, AAD π and 3 r 3 r D π ) is an important case of undecidable fragment, very close to the decidability/undecidability border [START_REF] Bresolin | Decidable and Undecidable Fragments of Halpern and Shoham's Interval Temporal Logic: Towards a Complete Classification[END_REF].

Syntax and Semantics of PI and its Fragments

Point and Interval Relations

Given a linearly ordered set D = D, < , we call the elements of D points and define an interval as an ordered pair [a, b] of points in D, where a < b. Now, as we have mentioned above, there are 13 possible relations, including equality, between any two intervals. From now on, we call these interval-interval relations. Besides, there are 3 different relations that may hold between any two points (before, equal, and after), called hereafter point-point relations, and 5 different relations that may hold between a point and an interval and vice-versa, namely before, beginning point, during, ending point, and after, called hereafter point-interval relations. Intuitively, our language will follow the same principle as the logic HS, discussed in the previous section: one modal operator for each one of the 19 relations, excluding the equalities between points and between intervals. To provide a uniform and simple notation, we first distinguish among two main types of modal operators: those evaluated at points, denoted by single square brackets , and those evaluated at intervals, denoted by double square brackets . Now, consider an interval [b, c]: it generates a partition of the set D into five regions (see [START_REF] Ligozat | On generalized interval calculi[END_REF]): the region 0, of those points before b, the region 1 that contains b only, the region 2 (between b and c), 3 (only c), and 4 (the remaining regions). Using that notation, for k ∈ {0, 1, 2, 3, 4}, a point modality may belong to one of two categories: 'point to point', of the type k , that refers to any point in the relation k with the current one -in which case the regions 1, 2, 3 coincide and we use the number 2 to indicate any of them -and 'point to interval', of the type kk , that refers to any interval such that its beginning point is in the region k, and its ending point in the region k , with respect to the current point. Likewise, an interval modality can be of 'interval to point' type k referring to any point in the area k w.r.t. the current interval, or of 'interval to interval' type kk , in which case it becomes a syntactic variation of the respective HS modality in the strict semantics.

Syntax and Semantics of the Point-Interval Logic PI

The language of the Point-Interval Logic PI comprises the classical connectives ¬ and ∨ (the rest are considered definable), two sorts of propositional letters, namely the set of point propositional letters AP po and the set of interval ones AP int , and unary modalities of each of the types specified above. For technical convenience we will assume that each of AP po and AP int is a copy of the set of propositional letters AP from the language of HS. We will denote typical elements of AP by p, q, . . ., respective typical elements of AP po by p po , q po , . . ., and respective typical elements of AP int by p int , q int , . . ..

The logic PI has two sorts of formulae: point formulae and interval formulae. Point formulae are obtained by the following grammar:

ϕ po ::= p po | ¬ϕ po | ϕ po ∨ ψ po | pp ϕ po | pi ϕ int ,
where pp represent any point-to-point modality, and pi is any point-to-interval modality. Similarly, interval formulae are formed by the following grammar:

ϕ int ::= p int | ¬ϕ int | ϕ int ∨ ψ int | ii ϕ int | ip ϕ po ,
where the modal operators are interval-to-point or interval-to-interval. The formulae of the type pp ϕ po , pi ϕ int , ip ϕ po , and ii ϕ int are called (respectively, point or interval) diamond formulae. The respective box formulae are defined, as usual, as their duals, e.g. [ij]ψ := ¬ ij ¬ψ 4 . Lastly, a PI formula is a point-formula or an interval-formula. • M, a p po iff p po ∈ V po (a);

• M, a 0 ϕ iff there exists b < a such that M, b ϕ;

• M, a 4 ϕ iff there exists b > a such that M, b ϕ;

• M, a 00 ϕ iff there exist b, c such that b < c < a, and that M, [b, c] ϕ;

• M, a 02 ϕ iff there exist b, c such that b < c = a, and that M, [b, c] ϕ;

• M, a 04 ϕ iff there exist b, c such that b < a < c, and that M, [b, c] ϕ;

• M, a 24 ϕ iff there exist b, c such that b = a < c, and that M, [b, c] ϕ;

• M, a 44 ϕ iff there exist b, c such that a < b < c, and that M, [b, c] ϕ, and respectively:

• M, [a, b] p int iff p int ∈ V int ([a, b]); • M, [a, b] 0 ϕ iff there exists c < a such that M, c ϕ; • M, [a, b] 1 ϕ iff M, a ϕ; • M, [a, b]
2 ϕ iff there exist c such that a < c < b, and that M, c ϕ;

• M, [a, b] 3 ϕ iff M, b ϕ; • M, [a, b]
4 ϕ iff there exist c such that b < c, and that M, c ϕ, An interval-(resp., point-) PI-formula φ is satisfiable if there exists a PI-model and an interval (resp., a point) in it that satisfies φ. Note that the clauses for the 'interval-to-interval' modalities are identical to those for the HS modalities in the strict semantics.

Expressiveness of fragments of PI

In this section we systematically compare the expressiveness of PI and its fragments to that of HS and its fragments.

Transformations between models of PI and HS

In order for us to compare the expressiveness of fragments of PI and HS we need to specify transformations of two-sorted PI models into HS-models, and vice-versa.

(M ) = D, I(D), V po , V int .
Further, with a slight abuse of notation we will use τ and σ to denote respec-tive syntactic translations of formulae of the one language to the other, such that the translation τ maps each the propositional letters p po and p int to p, while the translation σ splits into two parts: σ p , producing point formulae by mapping each propositional letter p to p po and σ i , producing interval formulae by mapping each propositional letter p to p int . Note that τ and σ are so far just notation; further we will define different such translations, to match different fragments of HS and PI.

Comparing expressiveness of some fragments of PI and HS

Now, we can compare the expressive power of standard interval logics and twosorted ones, by following the general terminology for comparing expressiveness of logics with respect to the transformations τ and σ, as follows.

Let L be any fragment of PI, and L any fragment of HS; we say that L is at least as expressive as L, denoted by L L , iff τ can be extended to a truth preserving syntactic translation from L to L , that is, one that maps every L formula to L formula, such that:

(i) for every PI-model M , point a ∈ M and a point formula ψ of L: M, a |= ψ iff τ (M ), [a, a] |= τ (ψ), (ii) for every PI-model M , interval [a, b] ∈ M and an interval formula ψ of L: M, [a, b] |= ψ iff τ (M ), [a, b] |= τ (ψ).
Likewise, let L be a fragment of HS and L a fragment of PI. We say that L is at least as expressive as L, denoted L L , iff σ can be extended to a truth preserving syntactic translation from L to L , that is, one that maps every L formula to L formula, such that: In each of the cases above we say that L is more expressive than L, denoted L ≺ L if L L , and not L L. Respectively, we say that L and L are expressively incomparable 6 if neither L L nor L L, and they are expressively equivalent, denoted by L ≡ L , if and only if L L and L L.

Hereafter we only consider in detail the fragment PI mix of PI that comprises the inter-sort modalities, that is, the 'point-to-interval' and the 'interval-to-point' ones, and some notable fragments of it. We consider PI mix to be the most interesting of the fragments of PI because it captures precisely the expressiveness of the interaction between points and intervals. We also denote by PI mix -k the fragment of PI mix devoid of the interval-to-point modal operator k , and by PI mix -kk the fragment of PI mix devoid of the point-to-interval modal operator kk . Moreover, for any two-sorted language L, we write L > to denote the sub-language

HS AAEE PI mix PI mix -2 PI mix -04 PI mix -2 , 04 ≡PNL π 3 r 3 l D π AB PI mix -04 > Figure 1
. Some interesting fragments of PI and their expressiveness relation with fragments of HS.

of L that only retains the 'future' operators of L, that is, those that refer to the regions to the right of the current point or interval. In Fig. 1 we have indicated expressiveness relations between each pair of fragments of HS and PI connected by a line, where the relation applies between the lower to the higher fragment. With a mild abuse of notation, we will use ≺ and to compare two fragments of PI or of HS, in the obvious way (only syntactic translation needed). Proof All relations on pairs of fragments of HS and on pairs of fragments of PI are trivial. As for the remaining cases, it is sufficient to define suitable truthpreserving translations τ and σ, as discussed above. We do that below for each case. Notice that, in the non-strict semantics π is definable in a HS-fragment in presence of B (π

≡ [B]⊥) or E (π ≡ [E]⊥). Also, observe that 3 r ϕ ≡ E (ϕ ∧ π) ∨ A ϕ and 3 l ϕ ≡ A (ϕ ∨ E (π ∧ ϕ)) (a similar definition can be devised in presence of B instead of E ).
-PI mix AAEE:

The following translation τ works (the easy details are left to the reader).

• τ ( 00 ψ) = π ∧ 3 l (¬π ∧ 3 l (¬π ∧ τ (ψ))); • τ ( 02 ψ) = π ∧ 3 l (¬π ∧ τ (ψ)); • τ ( 04 ψ) = π ∧ 3 r (¬π ∧ E τ (ψ)); • τ ( 24 ψ) = π ∧ 3 r (¬π ∧ τ (ψ)); • τ ( 44 ψ) = π ∧ 3 r (¬π ∧ 3 r (¬π ∧ τ (ψ))); • τ ( 0 ψ) = ¬π ∧ 3 l (¬π ∧ 3 l (π ∧ τ (ψ))); • τ ( 1 ψ) = ¬π ∧ 3 l (π ∧ τ (ψ)); • τ ( 2 ψ) = ¬π ∧ E (¬π ∧ 3 l (π ∧ τ (ψ)));
• τ ( 3 ψ) = ¬π ∧ 3 r (π ∧ τ (ψ)); • τ ( 4 ψ) = ¬π ∧ 3 r (¬π ∧ 3 r (π ∧ τ (ψ))),
Note that the relationship PI mix AABB holds, too, by symmetry; nevertheless, using AAEE gives us the decidability of PI mix over the natural numbers -the relationship PI mix AABB allows us to say that PI mix is decidable over the (less interesting) set of negative natural numbers [START_REF] Montanari | Maximal decidable fragments of Halpern and Shoham's modal logic of intervals[END_REF].

-PI mix -04 3 r 3 l D π : For this claim it suffices to modify the definition of τ from the previous case as follows, taking into account that 04 is no longer part of the language:

• τ ( 2 ψ) = ¬π ∧ D (π ∧ τ (ψ));
-PI mix -04 > AB: Again, by modifying τ above:

• τ ( 1 ψ) = ¬π ∧ B (π ∧ τ (ψ)); • τ ( 2 ψ) = ¬π ∧ B (¬π ∧ A (π ∧ τ (ψ))). -PI mix -2 , 04 ≡PNL π : To show PI mix -04 , 2
PNL π we define τ as in the translation to AAEE above. To show PNL π PI mix -04 , 2 we define σ as follows:

• σ p (3 r ψ) = 24 σ i (ψ) ∨ σ p (ψ);

• σ p (3 l ψ) = 02 σ i (ψ) ∨ σ p (ψ); • σ i (3 r ψ) = 3 ( 24 σ i (ψ) ∨ σ p (ψ)); • σ i (3 l ψ) = 1 ( 02 σ i (ψ) ∨ σ p (ψ)) • σ p (π) = , σ i (π) = ⊥. 2
We note that the expressive embeddings above are not claimed here to be strict. Proving their strictness requires proving respective non-expressibility results (which, in general, depend on the particular class of structures in which the languages are interpreted) for which there is no space here. However, related classification of the expressive power of fragments of HS has recently appeared in [START_REF] Della Monica | Expressiveness of the Interval Logics of Allens Relations on the Class of all Linear Orders: Complete Classification[END_REF], and some of the expressive embedding results above can be proven strict by using the modeltheoretic techniques applied there.

Decidability and complexity of fragments of PI

Clearly PI is at least as expressive as HS, and therefore its satisfiability problem is undecidable over most interesting classes of linearly ordered sets. Also, the more expressive fragments of PI are at least as expressive as some known undecidable fragments of HS, and thus are undecidable themselves. For example, any fragment of PI including at least the pair of modalities 34 , 22 (resp., the modality 22 , or the pair of modalities 14 , 03 ) is undecidable in every interesting class of models, as it includes the HS-fragment AD (resp., O, BE). On the other hand, a number of fragments of PI are readily embeddable in already known decidable fragments of HS. Still, several fragments of PI give rise to essentially new decidability and complexity problems. Because of space constraints, we will consider in detail only one such case.

Some complexity bounds for PI mix and its fragments

Here we use the comparative expressiveness results from the previous section to immediately obtain results on decidability and complexity upper bounds of fragments of PI, by using respective known results for fragments of HS.

Proposition 5.1 (i)

The satisfiability problem for PI mix interpreted in the class of all finite models and in the class of models based on the set of natural numbers N is decidable, but with a non-elementary time complexity upper bound [START_REF] Montanari | Maximal decidable fragments of Halpern and Shoham's modal logic of intervals[END_REF].

(ii) The satisfiability problem for PI mix -04 > , interpreted in each of the classes of finite, discrete, dense, all linearly ordered models, as well as over models based on N, is decidable in EXPSPACE [START_REF] Bresolin | What's decidable about Halpern and Shoham's interval logic? the maximal fragment abbl[END_REF];

(iii) The satisfiability problem for PI mix -2 , 04 , in each of the classes of all finite, discrete, dense, and all linearly ordered models, as well as over models based on N, is NEXPTIME-complete [START_REF] Bresolin | Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions[END_REF].

Note that matching lower bounds for most of these cases are not known yet, because PI mix and its fragments do not have precise expressively matching fragments of HS.

In the rest of this section we will adapt model-theoretic arguments used in [START_REF] Bresolin | Metric propositional neighborhood logics on natural numbers[END_REF][START_REF] Bresolin | Propositional interval neighborhood logics: Expressiveness, decidability, and undecidable extensions[END_REF] to obtain a new decidability and complexity result for the satisfiability problem for PI mix -2 interpreted over finite models by proving bounded-model property with respect to models of exponential size. For that we will use the more general notion of fulfilling labeling structures.

Fulfilling labeling structures for PI mix -2

To begin with, note that satisfiability of an interval formula ϕ is equivalent to satisfiability of the point formula 24 ϕ; therefore it suffices to consider satisfiability of point formulas. Also, notice that two of the interval-to-point modalities are definable in terms of the others:

4 ψ ≡ 3 24 3 ψ, 0 ψ ≡ 1 02 1 ψ,
and, therefore, we will treat them as shortcuts. Similarly, two of the point-to-interval modalities are definable, too: 44 ψ ≡ 24 3 24 ψ, 00 ψ ≡ 02 1 02 ψ.

Definition 5.2

The closure of ϕ is the set CL(ϕ) of all subformulae of ϕ and their negations, where we identify every ¬¬ψ with ψ. We denote by CL po (ϕ) the subset of point formulae of CL(ϕ) and by CL int (ϕ) the subset of interval formulae of CL(ϕ).

Definition 5.3 A point ϕ-atom is a set A ⊆ CL po (ϕ) such that for every ψ ∈ CL po (ϕ), ψ ∈ A iff ¬ψ ∈ A and for every

ψ 1 ∨ ψ 2 ∈ CL po (ϕ), ψ 1 ∨ ψ 2 ∈ A iff ψ 1 ∈ A or ψ 2 ∈ A.
An interval ϕ-atom is defined likewise, using CL int (ϕ) instead of CL po (ϕ).

We Hereafter, by 'labeling structure' we will mean a labeling structure for some formula ϕ.

Note that every interval model M induces a LS, with labeling functions:

ψ ∈ L po (a) iff M, a ψ and ψ ∈ L int ([a, b]) iff M, [a, b] ψ.
Labeling structures can be thought of as quasi-models, in which the truth of formulae containing no modal operators is determined by the labeling functions. Furthermore, the labeling functions respect the semantics of the box operators. To obtain 'true models', we must also guarantee that the labeling is in accordance with the semantics of the diamond operators, too. To this end, we introduce the following notion. (ii) The set of diamond formulas of the type 02 ξ or 24 ξ in a given modal type R(a) can be satisfied by using at most m distinct endpoints of intervals.

For lack of space we have to omit the proof of the next, main technical result.

Corollary 5.11 Satisfiability of PI mix

-2 on the class of all finite linear orderings is decidable in NEXPTIME, and hence it is NEXPTIME-complete.

Small ultimately periodic model property of PI mix

-2 on N

Here, we will extend the previous result to decidability of PI mix -2 on N. Again, for lack of space, we can only provide a sketch. Definition 5.12 An LS L = (N, I(N), L po , L int ) is ultimately periodic (UPLS) with prefix length K ≥ 0 and period length P if L po (c+P ) = L po (c) for every point c ≥ K and for every interval [c, d]:

• If c ≥ K, then L int ([c + P, d + P ]) = L int ([c, d]); • If d ≥ K, then L int ([c, d + P ]) = L int ([c, d]),
Note that every finite LS can be regarded as an UPLS with a period length 0. Also, note that every UPLS is finitely representable: it suffices to define its labeling functions only on all points c < K +P and on all intervals [c, d] such that d < K +P or d < K + 2P and K < c < K + P , and then it can be uniquely extended by periodicity.

Claim 5.13 (Small Periodic Model Property) If ϕ is any formula of PI mix -2 satisfiable in N, then there exists a (possibly finite) ultimately periodic FLS satisfying ϕ with lengths of the prefix and of the period at most exponential in m = |CL(ϕ)|.

Proof [sketch] Given an interval model based on N and satisfying ϕ, we take its corresponding FLS and transform it to an ultimately periodic FLS for ϕ, by identifying sufficiently long prefix and period in it, and then modifying the rest of the model to make it ultimately periodic. That produces an LS which we make a fulfilling one by applying defect-repairing technique similar to the one in the proof of Lemma 5.9, but now fixing simultaneously all defects involving points on the same periodic orbit, and in a uniform way. Once the ultimately periodic FLS for ϕ is obtained, we reduce both the prefix and the period down to size, by applying again the defect-repairing technique in a uniform way. Thus, the satisfiability problem for PI mix -2 over N is NEXPTIME-complete, too. 2

Concluding remarks

In this paper we have considered a new approach to interval logics where time instants (points) and time intervals are treated as separate sorts, and have introduced the two-sorted point-interval logic PI that formalizes that approach. We have then focused on its fragment PI mix , involving only the inter-sort modalities and its subfragments, and have analyzed the expressiveness of its fragments with respect to fragments of HS. Using results and adapting techniques for the latter, and we have obtained some decidability and complexity results for the former.

A number of open problems remain, including: determining the decidability status and exact complexity of the satisfiability for the fragments of PI on the most natural classes of models (based on all, dense, discrete, finite, etc. linear models) and obtaining complete classification of these fragments with respect to their expressiveness, analogous to (and generalizing) the one for the fragments of HS recently completed in [START_REF] Della Monica | Expressiveness of the Interval Logics of Allens Relations on the Class of all Linear Orders: Complete Classification[END_REF]. The current work is intended as a beginning of their systematic exploration. CORE project, funded by the Danish Natural Science Research Council. We also thank the reviewers for some corrections and useful remarks.

A

  point-interval structure is a pair F = D, I(D) where D = D, < is a linear order and I(D) is the set of all strict intervals in D. A PI-model is a tuple M = (D, I(D), V po , V int ) where (D, I(D) is a point-interval structure and V po : D → 2 APpo and V int : I(D) → 2 AP int are valuations 5 assigning to each point (respectively, interval) the set of point (respectively, interval) propositional letters that are true of it. The truth (satisfaction) relation is defined in a PI-model by a mutual recursion on point and interval formulae as follows (the clauses for the classical connectives are standard):

First

  , let M = (D, I(D), V po , V int ) be a point-interval model based on some linearly ordered domain D = D, < . The corresponding non-strict HS-model τ (M ) is obtained by taking the set of all non-strict intervals over D: I(D) + = {[a, b] | a, b ∈ D, a ≤ b} and defining V as follows. For each proper interval [a, b], where a < b, we put V([a, b]) = {p ∈ AP | p int ∈ V int ([a, b]). Likewise, for each point interval [a, a] we put V([a, a]) = {p ∈ AP | p po ∈ V po (a). Conversely, given any HS-model M = D, I(D) + , V , the corresponding PI-model σ(M ) is obtained as follows. First, we consider the set of all strict intervals over D, I(D) = {[a, b] | a, b ∈ D, a < b}. Then, with every propositional letter p ∈ AP we associate two distinct new propositional letters: p po and p int . Now, for each p ∈ AP and all points a ∈ D such that p ∈ V([a, a]), we put p po ∈ V po (a); respectively, for all strict intervals [a, b] ∈ I(D) such that p ∈ V([a, b]), we put p int ∈ V int ([a, b]). Finally, we define σ

  (i) for every HS-model M , point interval [a, a] ∈ M and a formula ψ of L: M, [a, a] |= ψ iff σ(M ), a |= σ p (ψ), (ii) for every HS-model M , strict interval [a, b] ∈ M and a formula ψ of L: M, [a, b] |= ψ iff σ(M ), [a, b] |= σ i (ψ).

Theorem 4 . 1

 41 All expressiveness relations between fragments of HS and PI, represented in Fig. 1 hold true.

P

  . Balbiani et al. / Electronic Notes in Theoretical Computer Science 278 (2011) 31-45

Definition 5 . 4

 54 denote the set of point ϕ-atoms by A ϕ po and the set of interval ϕ-atoms by A ϕ int . Let ϕ be a PI mix -2 -formula. A labeling structure (LS) for ϕ is a tuple L = (D, I(D), L po , L int ), where (D, I(D)) is a point-interval structure and L po and L int are labeling functions defined respectively as L po : D → A ϕ po and L int : I(D) → A ϕ int and satisfying the following properties: • For every [b, c] ∈ I(D) and formula [24]ψ, if [24]ψ ∈ L po (b) then ψ ∈ L int ([b, c]); • For every a ∈ D, [b, c] ∈ I(D) such that b < a < c, and formula [04]ψ, if [04]ψ ∈ L po (a) then ψ ∈ L int ([b, c]); • For every [a, b] ∈ I(D) and formula [02]ψ, if [02]ψ ∈ L po (b) then ψ ∈ L int ([a, b]), • For every [a, b] ∈ I(D) and formula [[3]]ψ, if [[3]]ψ ∈ L int ([a, b]) then ψ ∈ L po (b); • For every [a, b] ∈ I(D) and formula [[1]]ψ, if [[1]]ψ ∈ L int ([a, b]) then ψ ∈ L po (a).

Definition 5 . 5

 55 An LS L = (D, I(D), L po , L int ) for a formula ϕ is fulfilling (a FLS) iff:• For every formula 24 ψ in CL po (ϕ) and point a ∈ D, if 24 ψ ∈ L po (a), then there exists an interval [a, b] ∈ I(D) such that ψ ∈ L int ([a, b]); • For every formula 02 ψ in CL po (ϕ) and point a ∈ D, if 02 ψ ∈ L po (a), then there exists an interval [b, a] ∈ I(D) such that ψ ∈ L int ([b, a]); • For every formula 04 ψ and point a ∈ D, if 04 ψ ∈ L po (a), then there exists an interval [b, c] ∈ I(D) such that b < a < c and ψ ∈ L int ([b, c]); • For every formula 1 ψ in CL int (ϕ) and interval [a, b] ∈ I(D), if 1 ψ ∈ L int ([a, b]), then ψ ∈ L po (a);

Definition 5 . 8

 58 Given an LS L = (D, I(D), L po , L int ) and a point a ∈ D, the modal type of a in L is the set R(a) consisting of all diamond point formulae in the label L po (a). We will call the formulae in R(a) requests at the point a.

5. 3

 3 Decidability and NEXPTIME-completeness of PI mix -2 in the finite Now we will show that every finite FLS satisfying a given formula of PI mix -2 can be cut down to size exponentially bounded above by the size of the formula. Let us define m = |CL(ϕ)|, and observe what follows: (i) If R(ϕ) is the set of modal types for points in L, then |R(ϕ)| ∈ O(2 m ).

Lemma 5 . 9 Corollary 5 . 10

 59510 Let L = (D, I(D), L po , L int ), where D = (D, <), be a finite FLS for a point formula ϕ, satisfying ϕ at some point a. Suppose that there exists a point e = a ∈ D with modal type R = R(e) such that there are at least m 2 + m + 1 points with modal type R before e, and at least m 2 + m + 1 such points after e in (D, <). Then, there exists a FLS L = ( D, I( D), Lpo , L int ) satisfying ϕ such that D = D \{e}. Satisfiability of a PI mix -2 -formula ϕ on the class of finite linear orderings is equivalent to its satisfiability on the class of finite linear orderings of size at most 2 m+1 (m 2 + m + 1), where m = |CL(ϕ)|.

•

  For every formula 3 ψ in CL int (ϕ) and interval[a, b] ∈ I(D), if 3 ψ ∈ L int ([a, b]), then ψ ∈ L po (b).A point (resp. interval) formula ψ is satisfied by a point (resp. interval) in a given FLS if it belongs to its label. A point (resp. interval) formula ψ is satisfied by an LFS if it is satisfied by some point (resp. interval) in it.

	Definition 5.6 Proposition 5.7 For every PI mix	-2 -formula, satisfiability in a point-interval
	model is equivalent to satisfiability in some fulfilling labeling structure.

P. Balbiani et al. / Electronic Notes in Theoretical Computer Science 278 (2011) 31-45

The typographic similarity between a box [ij] and an interval [a, b] is unfortunate, but should not cause confusion.

Usually, in modal logic valuations are functions assigning sets of possible worlds to propositional letters, and the functions defined here are called 'labeling functions', but in this paper we will use the term 'labeling function' for another purpose. P. Balbiani et al. / Electronic Notes in Theoretical Computer Science 278 (2011) 31-45

Note that these definitions are given in terms of the specific transformations τ and σ. However, it is easy to see that these definitions are as general as possible. P. Balbiani et al. / Electronic Notes in Theoretical Computer Science 278 (2011) 31-45

Acknowledgement

Guido Sciavicco was partially supported by the Spanish MEC project TIN2009-14372-C03-01, and the Spanish fellowship 'Ramon y Cajal' RYC-2011-07821. Valentin Goranko has been supported by a grant 24/2011-CSU 8.2.1 through the bilateral Programme for French-Danish scientific collaboration, and by the HYLO-