cs 편의 논문 | Gist.Science

Characterizations of Monadic Second Order Definable Context-Free Sets of Graphs

이 논문은 카운팅 모노다닉 2 차 논리 (CMSO) 로 정의 가능한 그래프 집합이 HR 문법으로 생성되는 문맥 자유 집합과, 유계 트리에너지를 가진 인식 가능한 집합 및 정의 가능한 전사를 통해 파싱 가능한 집합 등이 동치임을 증명합니다.

Radu Iosif, Florian Zuleger2026-03-11💻 cs

Interpolation and the Exchange Rule

이 논문은 교환 규칙 (가환성) 의 유무가 하위 구조 논리의 연역적 보간 성질과 대수적 구조의 병합 성질에 미치는 영향을 규명하여, 교환 규칙이 없는 경우 연속체 개수의 다양체가 해당 성질을 갖는 반면, 교환 규칙이 있는 경우 정확히 60 개의 다양체만이 해당 성질을 가진다는 결과를 제시합니다.

Wesley Fussner, George Metcalfe, Simon Santschi2026-03-11💻 cs

Normal Forms for Elements of ${}^*$ -Continuous Kleene Algebras Representing the Context-Free Languages

이 논문은 ${}^*$ -연속 키프네 대수와 폴리카이닉 대수의 텐서 곱을 통해 변수 바인더 없이 문맥 자유 표현을 다루기 위한 계산의 기초를 마련하고, 정규형 정리와 오토마타 표현을 활용하여 문맥 자유 언어를 표현하는 요소를 분석합니다.

Mark Hopkins, Hans Leiß2026-03-11💻 cs

Minimum Star Partitions of Simple Polygons in Polynomial Time

이 논문은 40 년 이상 해결되지 않았던 단순 다각형을 최소 개수의 별 모양 다각형으로 분할하는 문제를 다항 시간 알고리즘으로 해결한 것을 제시합니다.

Mikkel Abrahamsen, Joakim Blikstad, André Nusser + 1 more2026-03-11💻 cs

Summing the sum of digits

이 논문은 Mohanty 등 (2023) 의 genotype-phenotype 맵에서의 최대 돌연변이 강건성에 관한 정리를 바탕으로, 특정 정수 진법에서 숫자 합의 합계 함수에 대한 부등식을 재검토하고 일반화하며 기존 결과들을 유도해냅니다.

Jean-Paul Allouche, Manon Stipulanti2026-03-11💻 cs

Isomorphism for Tournaments of Small Twin Width

이 논문은 쌍너비 (twin width) 가 $k$ 인 토너먼트의 동형 판정 문제를 $k^{O(\log k)}n^{O(1)}$ 시간에 해결하는 알고리즘을 제시하여 해당 문제가 다항 시간에 해결 가능함을 증명하고, 토너먼트의 동형 판정이 조합론적 위스페르 - 레만 알고리즘으로는 해결되지 않으며 군론적 기법이 필수적임을 보여줍니다.

Martin Grohe, Daniel Neuen2026-03-11💻 cs

Asynchronous Composition of LTL Properties over Infinite and Finite Traces

이 논문은 비동기 소프트웨어 컴포넌트의 LTL 속성 검증을 위해 국소 속성을 글로벌 속성으로 변환하는 새로운 LTL 재작성 기법을 제안하고, 이를 OCRA 도구에 통합하여 무한 및 유한 트래이스에 대한 시맨틱 동등성과 최적화를 입증했습니다.

Alberto Bombardelli, Stefano Tonetta2026-03-11💻 cs

Pattern Avoidance for Fibonacci Sequences using $k$ -Regular Words

이 논문은 $k$ -정규 단어에서 특정 패턴을 피하는 경우의 수가 각각 $k$ -피보나치 점화식 $a_k(n)$ 과 $b_k(n)$ 을 따름을 증명하고, 관련 패턴의 변형에 대한 제곱된 피보나치 수에 대한 가설을 제시합니다.

Emily Downing, Elizabeth Hartung, Cody Lucido + 1 more2026-03-11💻 cs

Positional $ω$ -regular languages

이 논문은 $\omega$ -정규 언어의 위치성 (positionality) 을 완전히 특징짓는 패리티 오토마타를 제시하여 위치성 판별의 다항 시간 결정성, 다양한 게임 설정으로의 확장, 그리고 Kopczyński 의 추측을 해결하는 위치성 목표의 합에 대한 닫힘 성질 등을 증명합니다.

Antonio Casares, Pierre Ohlmann2026-03-11💻 cs

Representing Guardedness in Call-by-Value and Guarded Parametrized Monads

이 논문은 Uustalu 의 매개변수화된 모나드를 사용하여 값 호출 (call-by-value) 언어에서 효과 있는 함수 공간을 표현하는 방법을 제시함으로써, 순환의 잘 정의됨을 분류하는 가드드니스 (guardedness) 를 카테고리 내적 성질로 재해석합니다.

Sergey Goncharov2026-03-11💻 cs

Enumeration for MSO-Queries on Compressed Trees

이 논문은 SLP(직선 프로그램) 로 압축된 비순위 숲 (unranked forest) 에서 단항 2 차 논리 (MSO) 쿼리의 답을 나열할 때, 압축된 크기 |D|에 비례하는 전처리 시간과 출력에 비례하는 지연 시간으로 해결할 수 있음을 증명하여 기존 압축되지 않은 트리 기반 알고리즘보다 효율성을 크게 향상시켰습니다.

Markus Lohrey, Markus L. Schmid2026-03-11💻 cs

Causal Graph Dynamics and Kan Extensions

이 논문은 범주론의 칸 확장을 활용하여 국소적, 동기적, 결정론적인 특성을 가진 인과 그래프 역학이 글로벌 변환의 범주에 속함을 증명하고, 이를 통해 단조 인과 그래프 역학의 보편성을 규명합니다.

Luidnel Maignan, Antoine Spicher2026-03-11💻 cs

Using weakest application conditions to rank graph transformations for graph repair

이 논문은 그래프 제약 조건에서 유도된 '손상 지표' 및 '수리 지표' 적용 조건을 활용하여 그래프 변환 단계 전후의 제약 위반 수 변화를 정량화함으로써, 그래프 수리를 위한 변환 규칙을 잠재적 효과에 따라 순위 매기는 알고리즘을 제안하고 그 유효성과 확장성을 입증합니다.

Lars Fritsche, Alexander Lauer, Maximilian Kratz + 2 more2026-03-11💻 cs

Möbius-Transformed Trapezoidal Rule

이 논문은 가중 소보레프 공간에 정의된 함수에 대해 최적의 수렴 속도를 보장하는 모비우스 변환 사다리꼴 법칙을 제안하고, 이를 주기적 소보레프 공간으로의 변환을 통해 함수 근사, 무작위 알고리즘, 다변수 적분 등으로 확장하는 방법을 제시합니다.

Yuya Suzuki, Nuutti Hyvönen, Toni Karvonen2026-03-11💻 cs

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros

이 논문은 최대 차수가 $\Delta$ 인 그래프의 $q$ 색칠 수를 결정론적으로 근사 계산하는 알고리즘을 제시하여, 기존 $q=2\Delta$ 의 한계를 깨고 $q \ge (2-\eta)\Delta$ 조건에서 Potts 모델의 분할 함수가 0 이 아님을 증명함으로써 Barvinok 의 보간법을 활용한 다항 시간 근사 계산이 가능함을 보여줍니다.

Ferenc Bencs, Khallil Berrekkal, Guus Regts2026-03-11💻 cs

Optimizing QoS in HD Map Updates: Cross-Layer Multi-Agent with Hierarchical and Independent Learning

이 논문은 자율주행차의 HD 맵 업데이트 지연을 줄이기 위해 IEEE 802.11 의 CWmax 및 IFSn 파라미터를 포함한 교차계층 최적화와 계층적 독립 학습 기반의 다중 에이전트 방식을 제안하며, 이를 통해 기존 EDCA 대비 다양한 서비스에서 최대 87.3% 의 지연 시간 개선을 달성했음을 보여줍니다.

Jeffrey Redondo, Nauman Aslam, Juan Zhang + 1 more2026-03-11💻 cs

TIMotion: Temporal and Interactive Framework for Efficient Human-Human Motion Generation

이 논문은 단일 인체 기반 또는 분리 모델링 방식의 한계를 극복하기 위해 인과적 상호작용 주입, 역할 진화 스캐닝, 지역적 패턴 증폭 기법을 도입한 효율적이고 효과적인 인간 - 인간 모션 생성 프레임워크인 TIMotion 을 제안하고 InterHuman 및 InterX 데이터셋에서 우수한 성능을 입증합니다.

Yabiao Wang, Shuo Wang, Jiangning Zhang, Ke Fan, Jiafu Wu, Zhucun Xue, Yong Liu2026-03-11💻 cs

VisPoison: An Effective Backdoor Attack Framework for Tabular Data Visualization Models

이 논문은 표본 데이터 시각화 모델의 보안 취약점을 드러내기 위해 희귀 단어 패턴이나 첫 번째 단어 프롬프트와 같은 은밀한 트리거를 활용하여 민감 정보 유출, 오도성 시각화, 서비스 거부 공격을 수행하는 백도어 공격 프레임워크 'VisPoison'을 제안하고, 기존 방어 기법의 한계를 지적하며 보다 견고한 시스템의 필요성을 강조합니다.

Shuaimin Li, Chen Jason Zhang, Xuanang Chen, Anni Peng, Zhuoyue Wan, Yuanfeng Song, Shiwen Ni, Min Yang, Fei Hao, Raymond Chi-Wing Wong2026-03-11💻 cs

Open-World Task and Motion Planning via Vision-Language Model Genereated Constraints

이 논문은 비전 - 언어 모델이 생성한 이산적 및 연속적 제약 조건을 작업 및 운동 계획 (TAMP) 시스템에 통합하여 자연어 기반의 복잡한 장기 로봇 조작 과제를 해결하는 'OWL-TAMP'라는 새로운 접근법을 제안하고 그 유효성을 실험을 통해 입증합니다.

Nishanth Kumar, William Shen, Fabio Ramos, Dieter Fox, Tomás Lozano-Pérez, Leslie Pack Kaelbling, Caelan Reed Garrett2026-03-11💻 cs

"Should I Give Up Now?" Investigating LLM Pitfalls in Software Engineering

이 논문은 26 명의 소프트웨어 엔지니어를 대상으로 한 연구를 통해 LLM 의 부정확한 응답이 작업 포기 확률을 11 배 증가시키는 등 주요 실패 요인을 규명하고, 이를 극복하기 위한 프롬프트 정교화 등의 완화 전략과 향후 도구의 방향성을 제시합니다.

Jiessie Tie, Bingsheng Yao, Tianshi Li, Hongbo Fang, Syed Ishtiaque Ahmed, Dakuo Wang, Shurui Zhou2026-03-11💻 cs

← 이전 다음 →

cs