Online Monitoring of Metric Temporal Logic using Sequential Networks
이 논문은 사이버 - 물리 시스템의 메트릭 시계 논리 (MTL) 명세로부터 이산 및 밀집 시간 행동을 위한 순차적 네트워크를 구축하는 통합 기법을 제안하여, 효율적이고 확장 가능한 온라인 모니터링 프레임워크를 제공하며 기존 접근법 대비 뛰어난 성능과 확장성을 입증합니다.
💻 Category
cs
8731 편의 논문
Module checking of pushdown multi-agent systems
이 논문은 푸시다운 다중 에이전트 시스템 (PMS) 의 모듈 체킹 문제를 연구하여 ATL 에 대해서는 2EXPTIME-완전임을, ATL* 에 대해서는 4EXPTIME-완전임을 증명함으로써 ATL* 의 경우 기존 모델 체킹보다 지수적으로 높은 복잡도를 가짐을 보여줍니다.
Probabilistic Counters for Privacy Preserving Data Aggregation
이 논문은 모리스 카운터와 맥스지오 카운터와 같은 확률적 카운터가 추가적인 무작위화 없이도 개인의 사생활을 보호하면서 집계 데이터를 제공하는 효과적인 메커니즘이 될 수 있음을 증명하고, 이를 분산 설문 조사에 적용하는 방법을 제시합니다.
Homomorphisms of (n,m)-graphs with respect to generalised switch
이 논문은 (n,m)-그래프에 대한 일반화된 스위치 연산을 제안하고 이를 통해 호모모피즘의 기본 성질을 규명하며, 2004 년과 2012 년에 제기된 열린 문제들을 해결하고 범주론적 곱과 색수 이론을 확장하는 포괄적인 연구 결과를 제시합니다.
Excess demand in public transportation systems: The case of Pittsburgh's Port Authority
이 논문은 버스가 만석으로 탑승하지 못한 승객에 대한 데이터 누락으로 인한 편향을 보정하기 위해 잠재적 초과 수요를 식별하고 필터링하는 프레임워크를 제안하며, 이를 피츠버그 포트 오토리티의 실제 데이터를 적용하여 1 년 간의 초과 수요를 추정했습니다.
Implicit Biases in Refereeing: Lessons from NBA Referees
이 논문은 NBA 심판 데이터를 분석하여 홈팀 편향 (특히 플레이오프에서 두드러짐) 과 특정 선수에 대한 유리한 편향은 존재하지만, 특정 선수나 팀에 대한 부정적 편향 및 인종적 편향은 발견되지 않았음을 보고하며 팬데믹 이후 홈팀 편향이 감소한 점도 지적합니다.
Towards Selecting the Informative Alternative Relational Query Plans for Database Education
이 논문은 데이터베이스 교육에서 학습자가 쿼리 옵티마이저의 의사결정을 이해하는 데 도움이 되도록, 다양한 대체 실행 계획 중 가장 유익한 k 개의 계획을 선택하는 'TIPS' 문제를 정의하고 효율적인 근사 알고리즘을 제안하여 실증적으로 그 효과를 입증했습니다.
An Elementary Proof of the FMP for Kleene Algebra
이 논문은 변환 오토마타를 활용한 새로운 대수적 기법을 제시하여 클리니 대수 (Kleene Algebra) 의 유한 모델 성질 (FMP) 에 대한 초등적 증명을 제시하고, 이를 통해 유한 관계 모델에 대한 완전성을 확립함으로써 기존 결과를 일반화합니다.
Dyck Words, Pattern Avoidance, and Automatic Sequences
이 논문은 이진 문자열에서 $7/3$-제곱 자유성이 괄호 중첩 깊이의 유계를 보장함을 보이고, 투에 - 모르스 (Thue-Morse) 단어의 디크 (Dyck) 인자에 대한 명시적 특징을 규명하며 그 개수에 대한 엄밀한 상한과 하한을 증명합니다.
Proving Properties of -Representations with the Walnut Theorem-Prover
이 논문은 Walnut 정리 증명기를 활용하여 Frougny 와 Sakarovitch 의 고전 정리를 새로운 계산적 방식으로 재증명하고, 이를 통해 -표현에 관한 기존 및 새로운 결과들을 통일적이고 자동화된 방식으로 유도함을 보여줍니다.
Universal quantification makes automatic structures hard to decide
이 논문은 자동 구조에서 단일 보편 양화사 (universal quantifier) 를 제거할 때 최소 NFA 의 크기가 이중 지수적으로 증가할 수 있으며, 해당 언어의 공집합성 판정이 EXPSPACE-완전임을 증명하여 보편 양화사 제거에 대한 더 효율적인 접근법의 존재 가능성을 부정합니다.
Termination of Graph Transformation Systems via Generalized Weighted Type Graphs
이 논문은 이중 푸쉬아웃 (DPO) 그래프 변환 시스템의 종료성을 증명하기 위한 가중치 유형 그래프 기법을 정제하여, 그래프에 대한 접근법의 능력을 강화하고 다른 범주로 일반화하며 문헌에 등장하는 DPO 변형들을 허용하도록 개량합니다.
BOPIM: Bayesian Optimization for influence maximization on temporal networks
이 논문은 시간적 네트워크에서 영향력 극대화 문제를 해결하기 위해 커널 함수와 획득 함수를 개선한 베이지안 최적화 알고리즘인 BOPIM 을 제안하며, 기존 그리디 알고리즘과 유사한 성능을 유지하면서 최대 10 배 빠른 속도로 최적의 시드 노드 집합과 그 불확실성을 정량화할 수 있음을 입증합니다.
Robustness Over Time: Understanding Adversarial Examples' Effectiveness on Longitudinal Versions of Large Language Models
이 논문은 GPT, Llama, Qwen 등 주요 대규모 언어 모델 (LLM) 계열의 장기적 업데이트를 분석하여, 버전이 올라갈수록 항상 보안과 안전성이 향상되는 것은 아니며 오히려 특정 공격 유형에 대한 취약성이 심화되거나 모델 크기가 커져도 견고성이 균일하게 개선되지 않을 수 있음을 규명했습니다.
Cardinality and Representation of Stone Relation Algebras
이 논문은 가중치 그래프를 모델링하는 스톤 관계 대수에 카디널리티 공리를 일반화하여 관계 대수에 대한 더 간단한 공리 체계를 제시하고, 스톤 관계 대수의 표현 가능성 및 관계 대수화 조건을 연구합니다.
Characterizations of Monadic Second Order Definable Context-Free Sets of Graphs
이 논문은 카운팅 모노다닉 2 차 논리 (CMSO) 로 정의 가능한 그래프 집합이 HR 문법으로 생성되는 문맥 자유 집합과, 유계 트리에너지를 가진 인식 가능한 집합 및 정의 가능한 전사를 통해 파싱 가능한 집합 등이 동치임을 증명합니다.
Interpolation and the Exchange Rule
이 논문은 교환 규칙 (가환성) 의 유무가 하위 구조 논리의 연역적 보간 성질과 대수적 구조의 병합 성질에 미치는 영향을 규명하여, 교환 규칙이 없는 경우 연속체 개수의 다양체가 해당 성질을 갖는 반면, 교환 규칙이 있는 경우 정확히 60 개의 다양체만이 해당 성질을 가진다는 결과를 제시합니다.
Normal Forms for Elements of -Continuous Kleene Algebras Representing the Context-Free Languages
이 논문은 -연속 키프네 대수와 폴리카이닉 대수의 텐서 곱을 통해 변수 바인더 없이 문맥 자유 표현을 다루기 위한 계산의 기초를 마련하고, 정규형 정리와 오토마타 표현을 활용하여 문맥 자유 언어를 표현하는 요소를 분석합니다.
Minimum Star Partitions of Simple Polygons in Polynomial Time
이 논문은 40 년 이상 해결되지 않았던 단순 다각형을 최소 개수의 별 모양 다각형으로 분할하는 문제를 다항 시간 알고리즘으로 해결한 것을 제시합니다.
Summing the sum of digits
이 논문은 Mohanty 등 (2023) 의 genotype-phenotype 맵에서의 최대 돌연변이 강건성에 관한 정리를 바탕으로, 특정 정수 진법에서 숫자 합의 합계 함수에 대한 부등식을 재검토하고 일반화하며 기존 결과들을 유도해냅니다.