Recent advances in Multimodal Large Language Models (MLLMs) have enabled joint reasoning over financial textual and visual inputs. However, they still struggle with financial terminology, logical consistency, and numerical computations. Moreover, while commercial large models perform well on reasoning tasks, their high inference costs limit their scalable usage in real world financial applications. We thus propose a cost-effective framework, CLER, that combines contrastive retrieval with step-wise reflection to improve reasoning performance. Also, the reasoning cost is only generated in the test stage when using commercial large models. CLER leverages FinErrorSet, a dataset of 8,000+ mistake correction pairs from diverse open-source MLLMs. A fine grained retriever is trained to identify structurally relevant errors for self-correction through individual reflection. Experiments on three benchmarks show that CLER consistently outperforms other baselines. To our knowledge, CLER is the first framework to use cross-model errors for financial reasoning.

Xianda Zheng, Zijian Huang, Meng-Fen Chiang, Jiamou Liu, Yuan Fang, Michael J. Witbrock, Kaiqi Zhao. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Leader election serves a well-defined role in leader-based Byzantine Fault Tolerant (BFT) protocols. Existing reputation-based leader election frameworks for partially synchronous BFTs suffer from either protocol-specific proofs, narrow applicability, or unbounded recovery after network stabilization, leaving an open problem. This paper presents a novel protocol-independent abstraction formalizing generic correctness properties and effectiveness guarantees for leader election under partial synchrony, enabling protocol-independent analysis and design. Building on this, we design the Sliding Window Leader Election (SWLE) mechanism. SWLE dynamically adjusts leader nominations via consensus-behavior-based reputation scores, enforcing Byzantine-cost amplification. We demonstrate SWLE introduces minimal extra overhead to the base protocol and prove it satisfies all abstraction properties and provides superior effectiveness. We show, with a 16-server deployment across 4 different regions in northern China, SWLE achieves up to 4.2x higher throughput, 75% lower latency and 27% Byzantine leader frequency compared to the state-of-the-art solution under common Byzantine faults, while maintaining efficiency in fault-free scenarios.

While retrieval-augmented generation systems partially address the hallucination issues in large language models, it also introduces new vulnerabilities to knowledge corruption attacks. Adversaries exploit these vulnerabilities by poisoning documents provided by RAG system to manipulate LLM outputs. To counter this threat, we propose SecureCollaRAG, a Byzantine-tolerant collaborative RAG framework leveraging Multi-source Knowledge Validation Mechanism. Our approach enables agent system to securely verify document provenance through dynamic GNN-based credibility scoring, effectively preventing stealthy knowledge corruption attacks while preserving essential domain knowledge integrity. Through extensive evaluations and formal analysis, we demonstrate that SecureCollaRAG maintains robustness against attackers under non-IID data distributions.

Abstract A private data query system (PDQS) enables data consumers to access privately owned data while compensating data owners for their privacy loss. The two main tasks of a PDQS include procurement, i.e., collecting data from multiple data owners with an appropriate pricing scheme, and querying, i.e., aggregating the collected dataset for a query output while preserving data owners’ privacy. Existing PDQS are designed for unconditional queries over single-attribute data. In this paper, we design PrivCQ, a new PDQS that supports conditional queries over multi-dimensional data. To accommodate heterogeneous attribute-level privacy preferences, we introduce a new privacy concept, multi-dimensional personalised local differential privacy (m-PLDP), which specifies privacy requirements across multiple sensitive attributes for each data owner. For procurement, we propose total purchased privacy maximisation (TPPM), a principle linking query accuracy to m-PLDP. For query, we propose two techniques, attribute fusion and aggregation conditioning, to process conditional queries over multi-dimensional sensitive data. We design three query mechanisms that achieve m-PLDP under different paradigms and empirically validate them on three real-world datasets.

This paper presents Hydra, a dynamic BFT protocol that allows replicas to join and leave the system dynamically. It addresses the limitations of traditional static BFTs in managing membership changes and can be used to simplify the implementation of many features in modern blockchain applications. Hydra relies on weaker assumptions to achieve standard properties compared to the existing solution Dyno and introduces a configuration auto-transition protocol to ensure liveness. Through temporary configurations and explicitly defined replica responsibilities for request handling, Hydra pipelines membership requests alongside regular requests and realizes clarity, achieving a more efficient and smoother configuration transitions. It also employs a non-blocking configuration discovery mechanism, enabling new replicas to participate in consensus quickly. We formally prove Hydra's correctness under the dynamic BFT model. Experimental results demonstrate Hydra's ability to maintain throughput fluctuations within 5% during various replica join and leave scenarios, outperforming Dyno and existing BFT system supporting reconfiguration in both stability and efficiency. Hydra effectively manages scenarios that Dyno circumvents with stronger assumptions and quickly restores throughput to normal levels.

Large language models (LLMs) have demonstrated strong capabilities in language understanding and generation, and their potential in educational contexts is increasingly being explored. One promising area is learnersourcing, where students engage in creating their own educational content, such as multiple-choice questions. A critical step in this process is generating effective explanations for the solutions to these questions, as such explanations aid in peer understanding and promote deeper conceptual learning. However, students often find it difficult to craft high-quality explanations due to limited understanding or gaps in their subject knowledge. To support this task, we introduce ``ILearner-LLM,'' a framework that uses iterative enhancement with LLMs to improve generated explanations. The framework combines an explanation generation model and an explanation evaluation model fine-tuned using student preferences for quality, where feedback from the evaluation model is fed back into the generation model to refine the output. Our experiments with LLaMA2-13B and GPT-4 using five large datasets from the PeerWise MCQ platform show that ILearner-LLM produces explanations of higher quality that closely align with those written by students. Our findings represent a promising approach for enriching the learnersourcing experience for students and for leveraging the capabilities of large language models for educational applications.

Multi-agent path finding (MAPF) is a safety-critical scenario where the goal is to secure collision-free trajectories from initial to desired locations. However, due to system complexity and uncertainty, integrating learning-based controllers with MAPF is challenging and cannot theoretically guarantee the safety of the learned controllers. In response, our study proposes a verified safe multi-agent neural control (VSMANC) approach for MAPF, focusing on the unified training of Decentralized Control Barrier Functions (DCBF) and controllers to enhence safety. VSMANC enables all agents to concurrently learn controllers and DCBFs using a unified loss function designed to maximize safety, adhere to standard control policies, and incorporate path-finding-related heuristics. We also propose a formal verification-guided retraining process to both verify the properties of the learned DCBFs and generate counterexamples for retraining, thereby providing a verified safety guarantee. We validate our approach through shape formation experiments and UAV simulations, demonstrating significant improvements in safety and effectiveness in complex multi-agent environments.

Retrieval-Augmented Generation (RAG) systems combine external data retrieval with text generation and have become essential in applications requiring accurate and context-specific responses. However, their reliance on external data raises critical concerns about unauthorized collection and usage of personal information. To ensure compliance with data protection regulations like GDPR and detect improper use of data, we propose the Shadow RAG Auditing Data Provenance (S-RAG) framework. S-RAG enables users to determine whether their textual data has been utilized in RAG systems, even in black-box settings with no prior system knowledge. It is effective across open-source and closed-source RAG systems and resilient to defense strategies. Experiments demonstrate that S-RAG achieves an improvement in Accuracy by 19.9% (compared to the best baseline), while maintaining strong performance under adversarial defenses. Furthermore, we analyze how the auditor’s knowledge of the target system affects performance, offering practical insights for privacy-preserving AI systems. Our code is open-sourced online.

Sequential Resource Allocation with situational constraints presents a significant challenge in real-world applications, where resource demands and priorities are context-dependent. This paper introduces a novel framework, SCRL, to address this problem. We formalize situational constraints as logic implications and develop a new algorithm that dynamically penalizes constraint violations. To handle situational constraints effectively, we propose a probabilistic selection mechanism to overcome limitations of traditional constraint reinforcement learning (CRL) approaches. We evaluate SCRL across two scenarios: medical resource allocation during a pandemic and pesticide distribution in agriculture. Experiments demonstrate that SCRL outperforms existing baselines in satisfying constraints while maintaining high resource efficiency, showcasing its potential for real-world, context-sensitive decision-making tasks.

Ensuring character identity consistency across varying prompts remains a fundamental limitation in diffusion-based text-to-image generation. We propose CharCom, a modular and parameter-efficient framework that achieves character-consistent story illustration through composable LoRA adapters, enabling efficient per-character customization without retraining the base model. Built on a frozen diffusion backbone, CharCom dynamically composes adapters at inference using prompt-aware control. Experiments on multi-scene narratives demonstrate that CharCom significantly enhances character fidelity, semantic alignment, and temporal coherence. It remains robust in crowded scenes and enables scalable multi-character generation with minimal overhead, making it well-suited for real-world applications such as story illustration and animation.

Inverse Reinforcement Learning (IRL) learns a reward function to explain expert demonstrations. Modern IRL methods often use the adversarial (minimax) formulation that alternates between reward and policy optimization, which often lead to {\em unstable} training. Recent non-adversarial IRL approaches improve stability by jointly learning reward and policy via energy-based formulations but lack formal guarantees. This work bridges this gap. We first present a *unified* view showing canonical non-adversarial methods explicitly or implicitly maximize the likelihood of expert behavior, which is equivalent to minimizing the expected return gap. This insight leads to our main contribution: *Trust Region Reward Optimization* (TRRO), a framework that guarantees *monotonic* improvement in this likelihood via a Minorization-Maximization process. We instantiate TRRO into *Proximal Inverse Reward Optimization* (PIRO), a practical and stable IRL algorithm. Theoretically, TRRO provides the IRL counterpart to the stability guarantees of Trust Region Policy Optimization (TRPO) in forward RL. Empirically, PIRO matches or surpasses state-of-the-art baselines in reward recovery, policy imitation with high sample efficiency on MuJoCo and Gym-Robotics benchmarks and a real-world animal behavior modeling task.

Motor skills are performed through sequential movements rather than isolated actions. Yet, decoding these sequences from biosignals poses a significant challenge. To address this gap, this study transitions motor decoding from classifying movements in isolated time windows to segmenting sequential movements. The proposed algorithm segments the electromyography (EMG) sequence in a coarse-to-fine manner. It begins with frame-level segmentation and locating the approximate boundaries at the movement-level. A region-growing-inspired fusion strategy is then designed to incorporate the coarse segmentation and localization results for the fined output. Experiments on a self-collected EMG dataset demonstrate impressive results in segmenting movements for participant-dependent/independent setups (accuracy:$94.2\hbox{\%}/74.7\hbox{\%}$; dice coefficient:$92.5\hbox{\%}/61.7\hbox{\%}$; mean Intersection over Union:$80.9\hbox{\%}/51.9\hbox{\%}$). Further analysis shows the algorithm's ability to capture the natural rhythm in participants' movement sequences. This research paves the way for a deep understanding of motor sequences, which benefits various applications, such as rehabilitation engineering.

Leader-based BFT systems face potential disruption and performance degradation from malicious leaders, with current solutions often lacking scalability or greatly increasing complexity. In this paper, we introduce ABSE, an Adaptive Baseline Score-based Election approach to mitigate the negative impact of malicious leaders on leader-based BFT systems. ABSE is fully localized and proposes to accumulate scores for processes based on their contribution to consensus advancement, aiming to bypass less reliable participants when electing leaders. We present a formal treatment of ABSE, addressing the primary design and implementation challenges, defining its generic components and rules for adherence to ensure global consistency. We also apply ABSE to two different BFT protocols, demonstrating its scalability and negligible impact on protocol complexity. Finally, by building a system prototype and conducting experiments on it, we demonstrate that ABSE-enhanced protocols can effectively minimize the disruptions caused by malicious leaders, whilst incurring minimal additional resource overhead and maintaining base performance.

Designing suitable reward functions for numerous interacting intelligent agents is challenging in real-world applications. Inverse reinforcement learning (IRL) in mean field games (MFGs) offers a practical framework to infer reward functions from expert demonstrations. While promising, the assumption of agent homogeneity limits the capability of existing methods to handle demonstrations with heterogeneous and unknown objectives, which are common in practice. To this end, we propose a deep latent variable MFG model and an associated IRL method. Critically, our method can infer rewards from different yet structurally similar tasks without prior knowledge about underlying contexts or modifying the MFG model itself. Our experiments, conducted on simulated scenarios and a real-world spatial taxi-ride pricing problem, demonstrate the superiority of our approach over state-of-the-art IRL methods in MFGs.

Learnersourcing offers great potential for scalable education through student content creation. However, predicting student performance on learnersourced questions, which is essential for personalizing the learning experience, is challenging due to the inherent noise in student-generated data. Moreover, while conventional graph-based methods can capture the complex network of student and question interactions, they often fall short under cold start conditions where limited student engagement with questions yields sparse data. To address both challenges, we introduce an innovative strategy that synergizes the potential of integrating Signed Graph Neural Networks (SGNNs) and Large Language Model (LLM) embeddings. Our methodology employs a signed bipartite graph to comprehensively model student answers, complemented by a contrastive learning framework that enhances noise resilience. Furthermore, LLM's contribution lies in generating foundational question embeddings, proving especially advantageous in addressing cold start scenarios characterized by limited graph data. Validation across five real-world datasets sourced from the PeerWise platform underscores our approach's effectiveness. Our method outperforms baselines, showcasing enhanced predictive accuracy and robustness.

Abstract Lexicographic Ranking SuperMartingale (LexRSM) is a probabilistic extension of Lexicographic Ranking Function (LexRF), which is a widely accepted technique for verifying program termination. In this paper, we are the first to propose sound probabilistic extensions of LexRF with a weaker non-negativity condition, called single-component (SC) non-negativity. It is known that such an extension, if it exists, will be nontrivial due to the intricacies of the probabilistic circumstances. Toward the goal, we first devise the notion of fixability, which offers a systematic approach for analyzing the soundness of possibly negative LexRSM. This notion yields a desired extension of LexRF that is sound for general stochastic processes. We next propose another extension, called Lazy LexRSM, toward the application to automated verification; it is sound over probabilistic programs with linear arithmetics, while its subclass is amenable to automated synthesis via linear programming. We finally propose a LexRSM synthesis algorithm for this subclass, and perform experiments.

Recently there has been a large amount of research designing mechanisms for auction scenarios where the bidders are connected in a social network. Different from the existing studies in this field that focus on specific auction scenarios e.g. single-unit auction and multi-unit auction, this paper considers the following question: is it possible to design a scheme that, given a classical auction scenario and a mechanism M˜ suited for it, produces a mechanism in the network setting that preserves the key properties of M˜? To answer this question, we design meta-mechanisms that provide a uniform way of transforming mechanisms from classical models to mechanisms over networks and prove that the desirable properties are preserved by our meta-mechanisms. Our meta-mechanisms provide solutions to combinatorial auction scenarios in the network setting: (1) combinatorial auction with single-minded buyers and (2) combinatorial auction with general monotone valuation. To the best of our knowledge, this is the first work that designs combinatorial auctions over a social network.

The issue of fairness in AI arises from discriminatory practices in applications like job recommendations and risk assessments, emphasising the need for algorithms that do not discriminate based on group characteristics. This concern is also pertinent to auctions, commonly used for resource allocation, which necessitate fairness considerations. Our study examines auctions with groups distinguished by specific attributes, seeking to (1) define a fairness notion that ensures equitable treatment for all, (2) identify mechanisms that adhere to this fairness while preserving incentive compatibility, and (3) explore the balance between fairness and seller’s revenue. We introduce two fairness notions—group fairness and individual fairness—and propose two corresponding auction mechanisms: the Group Probability Mechanism, which meets group fairness and incentive criteria, and the Group Score Mechanism, which also encompasses individual fairness. Through experiments, we validate these mechanisms’ effectiveness in promoting fairness and examine their implications for seller revenue.

Dynamic networks are data structures that represent the interactions among various entities in real-world systems, with their topology and node properties evolving over time. However, prevailing approaches typically derive node embeddings through aggregating temporal neighbor nodes of adjacent several hops, thus failing to capture the long temporal dependencies in dynamic networks. Furthermore, existing research on dynamic networks focuses on node- and edge-level tasks, lacking the support of graph-level tasks. To address the limitations of current approaches, this paper proposes TP-GNN, a novel continuous dynamic graph neural network model intended for graph classification in dynamic networks, which offers two primary advantages: (1) TP-GNN captures the long temporal dependencies via a novel message-passing method based on the information flow among the nodes, and (2) it learns the network evolution process from edge order for accurate dynamic network analytics. We evaluate the performance of TP-GNN in five datasets, including a new dataset we created from a Java software project. The results show that our method outperforms state-of-the-art approaches in graph classification with an average improvement of 4.91% in terms of$F_{1}$Score11Codes and dataset are available at https://github.com/Jie-0828/TP-GNN..

Data augmentation is a popular technique to address the limited amount of training data available for machine learning models. However, existing approaches based on pretrained language models (PLMs) often suffer from limited diversity at the word or sub-word level and high costs associated with manual data collection and labeling. In this paper, we introduce a novel approach called DPTAK, which leverages the rich prior knowledge pre-learned by transformer-based PLMs to generate diverse and high-quality augmented data for text-to-data and data-to-text tasks. Unlike other methods, DPTAK retrieves associated knowledge with a given dataset and does not require manual data collection or labeling. Our experiments on E2E, WebNLG, and DART datasets demonstrate that DPTAK outperforms existing baseline models in terms of BLEU score by 0.37, 0.44, and 0.87, respectively, for the data-to-text task when applied with GPT-2. In text-to-data, DPTAK shows improvements of more than 0.44 BLEU score on E2E compared to other baseline methods. Moreover, DPTAK-augmented datasets exhibit the highest diversity scores among all existing data augmentation methods in data-to-text task, providing evidence of the effectiveness of our approach.

In an era where the capabilities of large language models (LLM) like ChatGPT are transforming digital communication, the challenge of directing these tools to create extensive, coherent narratives on an epic-scale has emerged as a critical frontier. This study introduces a novel methodology that fuses the spontaneous story generation of LLMs with the precision of auto-prompted reinforcement learning for crafting epic-scale, coherent narratives. Our approach starts with generating a skeletal outline, followed by iterative expansion, and blending operations for maintaining structural coherence in long-form content. To train the reinforcement learning model efficiently, we introduce an environment simulator that leverages a database of historical LLM interactions, circumventing the limitations of direct LLM interactions. This method enhances the decision-making process of the RL agent, enabling more effective prompt selection and narrative flow in extended texts. We validate its effectiveness through experiments, demonstrating the model’s ability to generate structured, narrative-driven text, thereby setting a new pathway towards AI-driven, large-scale storytelling.

Large language models (LLMs) such as ChatGPT and GPT-4 have demonstrated impressive capabilities in various generative tasks. However, their performance is often hampered by limitations in accessing and leveraging long-term memory, leading to specific vulnerabilities and biases, especially during long interactions. This paper introduces ChatLogic, an innovative framework specifically targeted at LLM reasoning tasks that can enhance the performance of LLMs in multi-step deductive reasoning tasks by integrating logic programming. In Chat-Logic, the language model plays a central role, acting as a controller and participating in every system operation stage. We propose a novel method of converting logic problems into symbolic integration with an inference engine. This approach leverages large language models’ situational understanding and imitation skills and uses symbolic memory to enhance multi-step deductive reasoning capabilities. Our results show that the ChatLogic framework significantly improves the multi-step reasoning capabilities of LLMs. The source code and data are available at https://github.com/Strong-AI-Lab/ChatLogic.

The sealed-bid auction enables bidders to secretly send their bids to the auctioneer, which compares all bids and publishes the winning one on the bid-opening day. This type of auction is friendly for protecting the bid privacy, and sufficiently fair for all bidders if the auctioneer acts faithfully. Unfortunately, the auctioneer may not always be trustworthy. The auctioneer has the ability to deliberately leak any bid information to a part of bidders for raising the final winning price based on the investigation. Meanwhile, the auctioneer can appoint any bidder as the winner, as long as the bidder accepts a higher winning price than the current highest bid. Since bidders cannot obtain any bid information from others, to the best of our knowledge, it is difficult to prevent bid leakage from the auctioneer, and support bidders to verify the bid comparison results without disclosing the winning bid, simultaneously. To alleviate these problems, we first construct a homomorphic encryption(HE)-based bid comparison circuit. All bidders can directly compute a cipher of the winning bid by using this circuit; hence, the winning bid does not need to be exposed to all bidders. Then, we propose a blockchain-based sealed-bid scheme (BSS) by integrating the circuit with commitment and zero-knowledge proof. The auctioneer only obtains the commitments of bids before the bid-opening day, and he has to prove that the winner's bid is the same as the plaintext of the bidders' computed cipher. Thus, the auctioneer can neither leak the bid information nor publish a higher winning price during in the auction. Detailed performance analysis shows that the computational complexity of BSS is linear with the binary length of bids.

Covert communication is an method that plays an important role in secure data transmission. The technology embeds covert information into data and propagates it through covert channels. The communication quality depends on the choice of channel and data embedding techniques. Recently, blockchain has emerged to become the preferred channel to carry out covert communication for its decentralization and anonymity features. Existing covert transaction methods are constructed transaction-by-transaction, which makes them immune to text analysis-based detection methods. However, it is easy to expose their features on the transaction graph level. Unfortunately, there is yet no method to detect covert transactions by the features of transaction graph. In this paper, we propose a covert transaction detection method based on graph structure. By analyzing the statistical features of graph structure for addresses, we can infer whether they are the participants of covert transactions. Furthermore, we design a protection method of covert transactions based on graph generation networks. By adjusting the structural features between different addresses, our method enhances the security of multiple interrelated covert transactions. Experimental analysis on the Bitcoin Testnet verifies the security and the efficiency of the proposed methods.

Non-intrusive load monitoring (NILM) aims to decompose aggregated electrical usage signal into appliance-specific power consumption and it amounts to a classical example of blind source separation tasks. Leveraging recent progress on deep learning techniques, we design a new neural NILM model {\em Multi-State Dual CNN} (MSDC). Different from previous models, MSDC explicitly extracts information about the appliance's multiple states and state transitions, which in turn regulates the prediction of signals for appliances. More specifically, we employ a dual-CNN architecture: one CNN for outputting state distributions and the other for predicting the power of each state. A new technique is invented that utilizes conditional random fields (CRF) to capture state transitions. Experiments on two real-world datasets REDD and UK-DALE demonstrate that our model significantly outperform state-of-the-art models while having good generalization capacity, achieving 6%-10% MAE gain and 33%-51% SAE gain to unseen appliances.

Unsupervised/self-supervised graph neural networks (GNN) are susceptible to the inherent randomness in the input graph data, which adversely affects the model's performance in downstream tasks. In this paper, we propose USER, an unsupervised and robust version of GNN based on structural entropy, to alleviate the interference of graph perturbations and learn appropriate representations of nodes without label information. To mitigate the effects of undesirable perturbations, we analyze the property of intrinsic connectivity and define the intrinsic connectivity graph. We also identify the rank of the adjacency matrix as a crucial factor in revealing a graph that provides the same embeddings as the intrinsic connectivity graph. To capture such a graph, we introduce structural entropy in the objective function. Extensive experiments conducted on clustering and link prediction tasks under random-perturbation and meta-attack over three datasets show that USER outperforms benchmarks and is robust to heavier perturbations.

This paper presents a novel perspective on the relationship between decentralization, a prevalent characteristic of multi-agent systems, and centralization, which involves imposing central control to achieve system-level objectives. Specifically, within the context of a networked opinion dynamic model, we introduce and discuss a framework for centralization. In this framework, a decentralized network consists of autonomous agents and a dynamic, unknown social structure. Centralization involves appointing specific agents in the network as access units, responsible for providing information and exerting influence within their local environments. We focus on centralization for the DeGroot model of opinion dynamics, aiming to achieve opinion convergence with the minimum number of access units. To accomplish this, we demonstrate that selecting access units to form a dominating set is crucial. Moreover, we propose algorithms based on a new local algorithmic framework called prowling to facilitate this process. Through systematic experiments conducted on both real-world and synthetic networks, we validate our algorithm and show its superiority over benchmark methods.

Diffusion auction is an emerging business model where a seller aims to incentivise buyers in a social network to diffuse the auction information thereby attracting potential buyers. We focus on designing mechanisms for multi-unit diffusion auctions. Despite numerous attempts at this problem, existing mechanisms either fail to be incentive compatible (IC) or achieve only an unsatisfactory level of social welfare (SW). Here, we propose a novel graph exploration technique to realise multi-item diffusion auction. This technique ensures that potential competition among buyers stay “localised” so as to facilitate truthful bidding. Using this technique, we design multi-unit diffusion auction mechanisms MUDAN and MUDAN-m. Both mechanisms satisfy, among other properties, IC and 1/m-weak efficiency. We also show that they achieve optimal social welfare for the class of rewardless diffusion auctions. While MUDAN addresses the bottleneck case when each buyer demands only a single item, MUDAN-m handles the more general, multi-demand setting. We further demonstrate that these mechanisms achieve near-optimal social welfare through experiments.

In the digital age, data is a valuable commodity, and data marketplaces offer lucrative opportunities for data owners to monetize their private data. However, data privacy is a significant concern, and differential privacy has become a popular solution to address this issue. Private data trading systems (PDQS) facilitate the trade of private data by determining which data owners to purchase data from, the amount of privacy purchased, and providing specific aggregation statistics while protecting the privacy of data owners. However, existing PDQS with separated procurement and query processes are prone to over-perturbation of private data and lack trustworthiness. To address this issue, this paper proposes a framework for PDQS with an integrated procurement and query process to avoid excessive perturbation of private data. We also present two instances of this framework, one based on a greedy approach and another based on a neural network. Our experimental results show that both of our mechanisms outperformed the separately conducted procurement and query mechanism under the same budget regarding accuracy.

Business process management focuses on the automatic discovery and optimisation of business process models for a wide range of business scenarios. At the same time, the development of natural language processing (NLP), in particular some large-scale pre-trained language models such as BERT and GPT, has recently achieved great success and become a milestone in many practical fields. We thus propose a new paradigm to automate business process model discovery directly from interview-based natural language documents by applying NLP technologies to the business process modeling area. To train the language models for the business process management domain, we create the Business Process Model and Textual Description (MaD) dataset, which contains 15 business categories and a total of 30,000 BPM-description pairs. Furthermore, we define the automatic as well as human-involved metrics to evaluate the quality of the MaD dataset. The experiment results show that the generated dataset is of high-quality, and suitable for high-level people with professional skills to read and understand. The dataset is available online11https://drive.google.com/drive/u/0/folders/1n0K9BmiDsXYCqB796MVebYBgWX2ruZpW.

Recent years have seen a growing interest in deep learning-based approaches to localize faults in software. However, existing methods have not reached a satisfying level of accuracy. The main reason is that the feature extraction of faulty code elements is insufficient. Namely, these deep learning-based methods will learn some features that are not relevant to fault localization, and thus ignore the features related to fault localization. We propose SupConFL, a new framework for statement-level fault localization. Our framework combines the statement-level abstract syntax tree with the statement sequence, and adopt controllable attention-based LSTM to locate the faulty elements. The training is done through contrastive learning between the faulty code and its fixed version. By comparing the faulty code with the fixed code, the model can learn richer features of the faulty code elements. Our experiments on Defects4j-1.2.0 dataset show that our method outperforms the current state-of-the-art. Specifically, SupConFL improves Top-1 score by 7.96% in comparison with the current state-of-the-art. In addition, our method has also achieved good results in cross-project experiments.

Anomaly detection is an important task that improves the maturity and stability of a software during its development. System logs record rich information about the running states of the software and reveal key insights of anomalous behaviors. This paper addresses anomaly detection using system log data and aims to resolve two challenges: First, different from most existing supervised learning-based anomaly detection methods that rely heavily on expensive, manually-curated labels, we aim to design an algorithm to make the most of scarce label information. Second, as a typical software system would contain very few anomalies, we aim to address the data imbalance issue which is often overlooked by existing studies. To address the challenges above, we propose LGLog, a semi-supervised anomaly detection framework that is based on system logs. First, LGLog transforms log sequences into graphs and employs an unsupervised graph learning model for pre-training. Then, LGLog mitigates the data imbalance issue by learning significant latent space representation of log events via reconstruction loss and node invariance loss, and further applies a weight balance method. Experiments indicate that LGLog outperforms compared approaches, and demonstrates the effectiveness of LGLog in the presence of scarce labels and imbalanced log data.

This paper is the first to use contrastive learning to improve the robustness of graph representation learning for signed bipartite graphs, which are commonly found in social networks, recommender systems, and paper review platforms. Existing contrastive learning methods for signed graphs cannot capture implicit relations between nodes of the same type in signed bipartite graphs, which have two types of nodes and edges only connect nodes of different types. We propose a Signed Bipartite Graph Contrastive Learning (SBGCL) method to learn robust node representation while retaining the implicit relations between nodes of the same type. SBGCL augments a signed bipartite graph with a novel two-level graph augmentation method. At the top level, we maintain two perspectives of the signed bipartite graph, one presents the original interactions between nodes of different types, and the other presents the implicit relations between nodes of the same type. At the bottom level, we employ stochastic perturbation strategies to create two perturbed graphs in each perspective. Then, we construct positive and negative samples from the perturbed graphs and design a multi-perspective contrastive loss to unify the node presentations learned from the two perspectives. Results show proposed model is effective over state-of-the-art methods on real-world datasets.

Diffusion auction refers to an emerging paradigm of online marketplace where an auctioneer utilises a social network to attract potential buyers. Diffusion auction poses significant privacy risks. From the auction outcome, it is possible to infer hidden, and potentially sensitive, preferences of buyers. To mitigate such risks, we initiate the study of differential privacy (DP) in diffusion auction mechanisms. DP is a well-established notion of privacy that protects a system against inference attacks. Achieving DP in diffusion auctions is non-trivial as the well-designed auction rules are required to incentivise the buyers to truthfully report their neighbourhood. We study the single-unit case and design two differentially private diffusion mechanisms (DPDMs): recursive DPDM and layered DPDM. We prove that these mechanisms guarantee differential privacy, incentive compatibility and individual rationality for both valuations and neighbourhood. We then empirically compare their performance on real and synthetic datasets.

Signed graphs model complex relations using both positive and negative edges. Signed graph neural networks (SGNN) are powerful tools to analyze signed graphs. We address the vulnerability of SGNN to potential edge noise in the input graph. Our goal is to strengthen existing SGNN allowing them to withstand edge noises by extracting robust representations for signed graphs. First, we analyze the expressiveness of SGNN using an extended Weisfeiler-Lehman (WL) graph isomorphism test and identify the limitations to SGNN over triangles that are unbalanced. Then, we design some structure-based regularizers to be used in conjunction with an SGNN that highlight intrinsic properties of a signed graph. The tools and insights above allow us to propose a novel framework, Robust Signed Graph Neural Network (RSGNN), which adopts a dual architecture that simultaneously denoises the graph while learning node representations. We validate the performance of our model empirically on four real-world signed graph datasets, i.e., Bitcoin_OTC, Bitcoin_Alpha, Epinion and Slashdot, RSGNN can clearly improve the robustness of popular SGNN models. When the signed graphs are affected by random noise, our method outperforms baselines by up to 9.35% Binary-F1 for link sign prediction. Our implementation is available in PyTorch1.

A data marketplace is an online venue that brings data owners, data brokers, and data consumers together and facilitates commoditisation of data amongst them. Data pricing, as a key function of a data marketplace, demands quantifying the monetary value of data. A considerable number of studies on data pricing can be found in literature. This article attempts to comprehensively review the state-of-the-art on existing data pricing studies to provide a general understanding of this emerging research area. Our key contribution lies in a new taxonomy of data pricing studies that unifies different attributes determining data prices. The basis of our framework categorises these studies by the kind of market structure, be it sell-side, buy-side, or two-sided. Then in a sell-side market, the studies are further divided by query type, which defines the way a data consumer accesses data, while in a buy-side market, the studies are divided according to privacy notion, which defines the way to quantify privacy of data owners. In a two-sided market, both privacy notion and query type are used as criteria. We systematically examine the studies falling into each category in our taxonomy. Lastly, we discuss gaps within the existing research and define future research directions.

Automated question quality rating (AQQR) aims to evaluate question quality through computational means, thereby addressing emerging challenges in online learnersourced question repositories. Existing methods for AQQR rely solely on explicitly-defined criteria such as readability and word count, while not fully utilising the power of state-of-the-art deep-learning techniques. We propose DeepQR, a novel neural-network model for AQQR that is trained using multiple-choice-question (MCQ) datasets collected from PeerWise, a widely-used learnersourcing platform. Along with designing DeepQR, we investigate models based on explicitly-defined features, or semantic features, or both. We also introduce a self-attention mechanism to capture semantic correlations between MCQ components, and a contrastive-learning approach to acquire question representations using quality ratings. Extensive experiments on datasets collected from eight university-level courses illustrate that DeepQR has superior performance over six comparative models.

Next POI recommendation intends to forecast users' immediate future movements given their current status and historical information, yielding great values for both users and service providers. However, this problem is perceptibly complex because various data trends need to be considered together. This includes the spatial locations, temporal contexts, user's preferences, etc. Most existing studies view the next POI recommendation as a sequence prediction problem while omitting the collaborative signals from other users. Instead, we propose a user-agnostic global trajectory flow map and a novel Graph Enhanced Transformer model (GETNext) to better exploit the extensive collaborative signals for a more accurate next POI prediction, and alleviate the cold start problem in the meantime. GETNext incorporates the global transition patterns, user's general preference, spatio-temporal context, and time-aware category embeddings together into a transformer model to make the prediction of user's future moves. With this design, our model outperforms the state-of-the-art methods with a large margin and also sheds light on the cold start challenges within the spatio-temporal involved recommendation problems.

Bin Sun, Shaoxiong Feng, Yiwei Li, Jiamou Liu, Kan Li. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

Traffic flow forecasting is a crucial task in urban computing. The challenge arises as traffic flows often exhibit intrinsic and latent spatio-temporal correlations that cannot be identified by extracting the spatial and temporal patterns of traffic data separately. We argue that such correlations are universal and play a pivotal role in traffic flow. We put forward spacetime interval learning as a paradigm to explicitly capture these correlations through a unified analysis of both spatial and temporal features. Unlike the state-of-the-art methods, which are restricted to a particular road network, we model the universal spatio-temporal correlations that are transferable from cities to cities. To this end, we propose a new spacetime interval learning framework that constructs a local-spacetime context of a traffic sensor comprising the data from its neighbors within close time points. Based on this idea, we introduce local spacetime neural network (STNN), which employs novel spacetime convolution and attention mechanism to learn the universal spatio-temporal correlations. The proposed STNN captures local traffic patterns, which does not depend on a specific network structure. As a result, a trained STNN model can be applied on any unseen traffic networks. We evaluate the proposed STNN on two public real-world traffic datasets and a simulated dataset on dynamic networks. The experiment results show that STNN not only improves prediction accuracy by 15% over state-of-the-art methods, but is also effective in handling the case when the traffic network undergoes dynamic changes as well as the superior generalization capability.

Norm emergence is a process where agents in a multi-agent system establish self-enforcing conformity through repeated interactions. When such interactions are confined to a social topology, several self-reinforcing substructures (SRS) may emerge within the population. This prevents a formation of a global norm. We propose incremental social instruments (ISI) to dissolve these SRSs by creating ties between agents. Establishing ties requires some effort and cost. Hence, it is worth to design methods that build a small number of ties yet dissolve the SRSs. By using the notion of information entropy, we propose an indicator called the BA-ratio that measures the current SRSs. We find that by building ties with minimal BA-ratio, our ISI is effective in facilitating the global norm emergence. We explain this through our experiments and theoretical results. Furthermore, we propose the small-degree principle in minimising the BA-ratio that helps us to design efficient ISI algorithms for finding the optimal ties. Experiments on both synthetic and real-world network topologies demonstrate that our adaptive ISI is efficient at dissolving SRS.

The concept of conventions has attracted much attention in the multi-agent system research. In this article, we study the emergence of conventions from repeated n -player coordination games. Distributed agents learn their policies independently and are capable of observing their neighbours in a network topology. We distinguish two types of information representation about the observations: gist trace and verbatim trace. We conjecture that learning based on the gist trace, which overlooks the details and focuses only on the general choice of action of a neighbourhood, should achieve efficient convention emergence. To this end, a novel learning method that makes use of the gist trace is proposed. The experimental results confirm that the proposed method establishes conventions much faster than the state-of-the-art learning methods across diverse settings of multi-agent systems. In particular, the use of gist trace derived at a low level of abstraction further improves the efficiency of convention emergence.

In existing ensemble learning algorithms (e.g., random forest), each base learner’s model needs the entire dataset for sampling and training. However, this may not be practical in many real-world applications, and it incurs additional computational costs. To achieve better efficiency, we propose a decentralized framework:Multi-Agent Ensemble.The framework leverages edge computing to facilitate ensemble learning techniques by focusing on the balancing of access restrictions (small sub-dataset) and accuracy enhancement. Specifically, network edge nodes (learners) are utilized to model classifications and predictions in our framework. Data is then distributed to multiple base learners who exchange data via an interaction mechanism to achieve improved prediction. The proposed approach relies on a training model rather than conventional centralized learning. Findings from the experimental evaluations using 20 real-world datasets suggest that Multi-Agent Ensemble outperforms other ensemble approaches in terms of accuracy even though the base learners require fewer samples (i.e., significant reduction in computation costs).

Prominent structural patterns such as small-world and core-periphery structures amount to some of the most important emergent characteristics of a social network. Yet little work is done to interpret these emergent phenomena in a unified way. Towards a unified interpretation framework, we connect the establishment of social patterns with social capital. Social capital captures the benefits that an individual gains from its social surrounding. We argue that individuals' desire to gaining higher social capital may give rise to important network properties. To validate this claim, we propose social capital game that mathematically conceptualizes bonding and bridging social capital. This framework allows us to regard individuals in a social network as learning agents who gain social capital through iteratively building interpersonal ties. The link-building decisions of these agents are guided by a multiagent reinforcement learning (MARL) algorithm which improves agents' capability through repeated game plays. We conduct a series of experiments which demonstrate (1) the collective behaviors of the agents give rise to salient social patterns, and (2) by varying agents' preferences to different forms of social capital, different types of social patterns emerge. In particular, bonding social capital plays a pivotal role in the formation of a community structure in the network while bridging social capital is instrumental to the emergence of core-periphery structure. Our work sheds light on the formation of complex network phenomena.

Private data query combines mechanism design with privacy protection to produce aggregated statistics from privately-owned data records. The problem arises in a data marketplace where data owners have personalised privacy requirements and private data valuations. We focus on the case when the data owners are single-minded, i.e., they are willing to release their data only if the data broker guarantees to meet their announced privacy requirements. For a data broker who wants to purchase data from such data owners, we propose the SingleMindedQuery (SMQ) mechanism, which uses a reverse auction to select data owners and determine compensations. SMQ satisfies interim incentive compatibility, individual rationality, and budget feasibility. Moreover, it uses purchased privacy expectation maximisation as a principle to produce accurate outputs for commonly-used queries such as counting, median and linear predictor. The effectiveness of our method is empirically validated by a series of experiments.

WiFi access points are sources of considerable security risks as the wireless signals have the potential to leak important private information such as passwords. This article examines the security issues posed by point-of-sale (POS) terminals which are widely used in WiFi-covered environments, such as restaurants, banks, and libraries. In particular, we envisage an attack model on passwords entered on POS terminals. We put forward the WiPOS, a password inference system based on wireless signals. Specifically, the WiPOS is a device-free system that uses two commercial off-the-shelf (COTS) devices to collect WiFi signals. Implementing a new keystroke segmentation algorithm and adopting support vector machine (SVM) classifiers with global alignment kernel (GAK), the WiPOS achieves improvement on both keystroke recognition and password prediction. The experimental results show that the WiPOS can achieve more than 73% accuracy for 6-digit password with the top 100 candidates. This article calls the community to take a closer look at the risks posed by the current ubiquitous WiFi devices.

Information brokers control information flow and hold dominating positions in a social network. We study how a team of individuals with heterogeneous influencing power may gain such advantageous position through establishing new links. In particular, a collaborative brokerage problem aims to find the smallest set of nodes for a team of individuals with different influencing power to cover the entire network. We phrase this problem as an extension to the classical graph domination problem and thus this problem is NP-hard. We show that a polynomial-time solution exists for directed trees. We then develop efficient algorithms over arbitrary directed networks. To evaluate the algorithms, we run experiments over networks generated using well-known random graph models and real-world datasets. Experimental results show that our algorithms produce relatively good solutions with faster speed.

Designing systems that make accurate forecasts based on time dependent data is always a challenging and significant task. In this regard, a number of statistics and neural network-based models have been proposed for analyzing and forecasting time series datasets. In this paper, we propose a novel machine learning model for handling and predicting multivariate time series data. In our proposed model we focus on supervised learning technique in which (1) some features of time series dataset exhibit periodic behaviour and (2) time t is considered as an input feature. Due to periodic nature of multivariate time series datasets, our model is a simple neural network where the inputs to the single output source are assumed to be in the form A sin(Bt + C)x as opposed to the standard form inputs Ax + B. We train our proposed model on various datasets and compare our model's performance with standard well-known models used in forecasting multivariate time series datasets. Our results show that our proposed model often outperforms other exiting models in terms of prediction accuracy. Moreover, our results show that the proposed model can handle time series data with missing values and also input data-values that are non-equidistant. We hope that the proposed model will be useful in fostering future research on designing accurate forecasting algorithms.

Community detection amounts to one of the key methods in handling social networks with the aim of capturing global patterns of a network. This paper focuses on a situation where the network is unknown, which would render existing algorithms unusable. We propose exploratory community detection which aims to detect communities by utilizing samples taken from diffusion process over the network. For this problem, we propose a neural-based algorithm that develops a matrix representation of the network structure. This matrix is then the input of a spectral clustering algorithm to reveal communities in the network. We perform experiments on real-world and synthetic data sets with simulated diffusion samples.The results reveal that our algorithm has strong empirical performance.

Core-periphery structure refers to a prevalent property exhibited by many real-world complex networks. The formulation and identification of a network core-periphery structure have been a challenging problem. A classical framework (BE) proposed by Borgatti and Everett defines a core-periphery partition of the network by aligning its nodes with a block model and has been a standard method for this task. This method, however, suffers from high computational costs which make it inapplicable to large networks. Realizing this limitation, we proposed a new framework, which aims to efficiently evaluate core-ness of nodes. Our framework builds a model for core-periphery classification by integrating small samples. The experimental results of six real-world networks shows that our methods can efficiently and effectively identify network core, achieving a running time of less than three hours for a network with about 220,000 nodes.

This paper focuses on the privacy risks of disclosing the community structure in an online social network. By exploiting the community affiliations of user accounts, an attacker may infer sensitive user attributes. This raises the problem of community structure deception (CSD), which asks for ways to minimally modify the network so that a given community structure maximally hides itself from community detection algorithms. We investigate CSD through an information-theoretic lens. To this end, we propose a community-based structural entropy to express the amount of information revealed by a community structure. This notion allows us to devise residual entropy minimization (REM) as an efficient procedure to solve CSD. Experimental results over 9 real-world networks and 6 community detection algorithms show that REM is very effective in obfuscating the community structure as compared to other benchmark methods.

Nonintrusive load monitoring (NILM) has attracted tremendous attention owing to its cost efficiency in electricity and sustainable development. NILM aims at acquiring individual appliance power consumption rates using an aggregated power smart meter reading. Each individual appliance's power consumption enables users to monitor their electricity usage habits for rational saving strategies. This is also a valuable tool for detecting failure in appliances. However, the major barriers facing NILM schemes are issues of accurately capturing the features of each appliance and decreasing the computing time. Motivated by these challenges, we propose a new, efficient, and accurate NILM scheme, consisting of a learning step and a decomposing step. In the learning step, we propose the fast search-and-find of density peaks (FSFDPs) clustering algorithm aimed at capturing the features of the power consumption patterns of appliances. In the decomposing step, we propose a genetic algorithm (GA)-based matching algorithm to estimate the power consumption of each individual appliance using the aggregated power reading. Using elitist and catastrophic strategies, this step reduces the searching space to achieve considerable efficiency. Experimental results using the reference energy disaggregation dataset (REDD) indicate that our proposed scheme promotes accuracy by 10% and reduces the decomposing time by half.

Interpersonal ties are pivotal to individual efficacy, status and performance in an agent society.This paper explores three important and interrelated themes in social network theory: the center/periphery partition of the network; network dynamics; and social integration of newcomers. We tackle the question: How would a newcomer harness information brokerage to integrate into a dynamic network going from periphery to center? We model integration as the interplay between the newcomer and the dynamics network and capture information brokerage using a process of relationship building. We analyze theoretical guarantees for the newcomer to reach the center through tactics; proving that a winning tactic always exists for certain types of network dynamics. We then propose three tactics and show their superior performance over alternative methods on four real-world datasets and four network models. In general, our tactics place the newcomer to the center by adding very few new edges on dynamic networks with ~14000 nodes.

Question answering (QA) has significantly benefitted from deep learning techniques in recent years. However, domain-specific QA remains a challenge due to the significant amount of data required to train a neural network. This paper studies the answer sentence selection task in the Bible domain and answer questions by selecting relevant verses from the Bible. For this purpose, we create a new dataset BibleQA based on bible trivia questions and propose three neural network models for our task. We pre-train our models on a large-scale QA dataset, SQuAD, and investigate the effect of transferring weights on model accuracy. Furthermore, we also measured the model accuracies with different answer context lengths and different Bible translations. We affirm that transfer learning has a noticeable improvement in the model accuracy. We achieved relatively good results with shorter context lengths, whereas longer context lengths decreased model accuracy. We also find that using a more modern Bible translation in the dataset has a positive effect on the task.

Influence maximization is a crucial problem in the analysis of large and complex networks. The problem asks for a set of nodes of a network from which message dissemination is maximized. This paper focuses on influence maximization from samples (IMFS) where the network is hidden. Instead, the input is a set of input-output samples of the influence function over a network. The recently proposed algorithm by Balkanski, Rubinstein, and Singer (BRS) for monotone submodular optimization achieves theoretically-tight optimization ratio. Empirically, however, no work is done to evaluate the actual performance of the BRS algorithm against parameters such as sample size, sample set size, and network topology. This paper provides an empirical analysis of algorithms for IMFS. In particular, we extends BRS by (1) factoring in effects caused by the complex network topology when approximating the marginal contribution of nodes and (2) removing constraints on the sampling distribution. We conduct experiments using two information diffusion models, and samples generated on both synthetic random networks and real-world networks. In general, our proposed algorithm significantly improves the output quality from the BRS algorithm.

In studies of social dynamics, cohesion refers to a group's tendency to stay in unity, which -- as argued in sociometry — arises from the network topology of interpersonal ties. We follow this idea and propose a game-based model of cohesion that not only relies on the social network, but also reflects individuals' social needs. In particular, our model is a type of cooperative games where players may gain popularity by strategically forming groups. A group is socially cohesive if the grand coalition is core stable. We study social cohesion in some special types of graphs and draw a link between social cohesion and a classical notion of structural cohesion by White and Harary. We then focus on the problem of deciding whether a given social network is socially cohesive and show that this problem is CoNP-complete. Nevertheless, we give two efficient heuristics for coalition structures where players enjoy high popularity and experimentally evaluate their performances.

By persistently gathering information over social networks, a person can extract detailed accounts of the lives of others and monitor their daily routines. Such surveillance behaviors have posed serious privacy concerns. This paper addresses the question, "who is surveilling you through social networking?". Viewing a network as interconnected agents who interact through posting and retrieving information, we provide a measure to quantify the level of attention a person pays towards another. This measure allows us to capture online interpersonal surveillance.

Network integration refers to a process of building links between two networks so that they dissolve into a single unified network. Togetherness measures the proximity of these two networks as they integrate; this notion is fundamental to social networks as it is relevant to important concepts such as trust, coherence and solidarity. In this paper, we study the algorithmic nature of network integration and formally introduce three notions of togetherness. We analyze the corresponding computational problems of network integration: Given two networks and a desired level of togetherness, build links between members of these networks so that the overall network meets the togetherness criterion. We analyze optimal solutions to this problem, describe several heuristics and compare their performance through experimental analysis.

An organisational structure consists of a network where employees are connected by working and social ties. Analysing this network, one can discover valuable insights into information flow within the organisation. Moreover, properly defined centrality measures reveal the distribution of power and, therefore, important individuals in the network. We develop this idea and propose a model that is consistent with management theory, and that captures main traits of large corporations. The carcass of the model is an organisational hierarchy. We extend it by allowing additional types of connections such as collaboration, consultation, and friendship. Having both reporting and non-reporting interpersonal ties, our model supports a multilevel approach to social networks. We then formally define power and stability in organisations. These notions enable us to analyse a range of organisational phenomena such as limited hierarchy height, restructuring through flattening, and impact of non-reporting ties. We support our framework with examples and case studies.

We study word structures of the form (D,<=,P) where D is either N or Z, <= is a linear ordering on D and P in D is a predicate on D. In particular we show: (a) The set of recursive omega-words with decidable monadic second order theories is Sigma_3-complete. (b) We characterise those sets P subset of Z that yield bi-infinite words (Z,<=,P) with decidable monadic second order theories. (c) We show that such "tame" predicates P exist in every Turing degree. (d) We determine, for P subset of Z, the number of predicates Q subset of Z such that (Z,<=,P) and (Z,<=,Q) are indistinguishable. Through these results we demonstrate similarities and differences between logical properties of infinite and bi-infinite words.

This paper studies algorithms for deciding the winners of two-player games played on directed graphs. We focus on the case when the underlying graphs are trees with back-edges and provide both theoretical and experimental analysis of this class of games. In particular, we present an algorithm that solves Büchi games played on trees with back-edges in time O(min{r·m, l+m}) where m is the number of edges, l is the sum of the distances from the root to all leaves and the parameter r is bounded by the height of the tree. We also show that parity games played on trees with back-edges can be solved in time O(l + m).

Several new undecidability results on isomorphism problems for automatic structures are shown: (i) The isomorphism problem for automatic equivalence relations is Π10-complete, (ii) The isomorphism problem for automatic trees of height n ≥ 2 is Π2n-30-complete, (iii) The isomorphism problem for automatic linear orders is not arithmetical.

This paper studies infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced using such operations are of finite degree and automatic over the unary alphabet (that is, they can be described by finite automata over the unary alphabet). We investigate algorithmic properties of such unfolded graphs given their finite presentations. In particular, we ask whether a given node belongs to an infinite component, whether two given nodes in the graph are reachable from one another and whether the graph is connected. We give polynomial-time algorithms for each of these questions. For a fixed input graph, the algorithm for the first question is in constant time and the second question is decided using an automaton that recognises the reachability relation in a uniform way. Hence, we improve on previous work, in which non-elementary or non-uniform algorithms were found.