An Elementary Proof of the FMP for Kleene Algebra
이 논문은 변환 오토마타를 활용한 새로운 대수적 기법을 제시하여 클리니 대수 (Kleene Algebra) 의 유한 모델 성질 (FMP) 에 대한 초등적 증명을 제시하고, 이를 통해 유한 관계 모델에 대한 완전성을 확립함으로써 기존 결과를 일반화합니다.
💻 Category
cs
3447 편의 논문
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 맵에서의 최대 돌연변이 강건성에 관한 정리를 바탕으로, 특정 정수 진법에서 숫자 합의 합계 함수에 대한 부등식을 재검토하고 일반화하며 기존 결과들을 유도해냅니다.
Isomorphism for Tournaments of Small Twin Width
이 논문은 쌍너비 (twin width) 가 인 토너먼트의 동형 판정 문제를 시간에 해결하는 알고리즘을 제시하여 해당 문제가 다항 시간에 해결 가능함을 증명하고, 토너먼트의 동형 판정이 조합론적 위스페르 - 레만 알고리즘으로는 해결되지 않으며 군론적 기법이 필수적임을 보여줍니다.
Asynchronous Composition of LTL Properties over Infinite and Finite Traces
이 논문은 비동기 소프트웨어 컴포넌트의 LTL 속성 검증을 위해 국소 속성을 글로벌 속성으로 변환하는 새로운 LTL 재작성 기법을 제안하고, 이를 OCRA 도구에 통합하여 무한 및 유한 트래이스에 대한 시맨틱 동등성과 최적화를 입증했습니다.
Pattern Avoidance for Fibonacci Sequences using -Regular Words
이 논문은 -정규 단어에서 특정 패턴을 피하는 경우의 수가 각각 -피보나치 점화식 과 을 따름을 증명하고, 관련 패턴의 변형에 대한 제곱된 피보나치 수에 대한 가설을 제시합니다.
Positional -regular languages
이 논문은 -정규 언어의 위치성 (positionality) 을 완전히 특징짓는 패리티 오토마타를 제시하여 위치성 판별의 다항 시간 결정성, 다양한 게임 설정으로의 확장, 그리고 Kopczyński 의 추측을 해결하는 위치성 목표의 합에 대한 닫힘 성질 등을 증명합니다.
Representing Guardedness in Call-by-Value and Guarded Parametrized Monads
이 논문은 Uustalu 의 매개변수화된 모나드를 사용하여 값 호출 (call-by-value) 언어에서 효과 있는 함수 공간을 표현하는 방법을 제시함으로써, 순환의 잘 정의됨을 분류하는 가드드니스 (guardedness) 를 카테고리 내적 성질로 재해석합니다.
Enumeration for MSO-Queries on Compressed Trees
이 논문은 SLP(직선 프로그램) 로 압축된 비순위 숲 (unranked forest) 에서 단항 2 차 논리 (MSO) 쿼리의 답을 나열할 때, 압축된 크기 |D|에 비례하는 전처리 시간과 출력에 비례하는 지연 시간으로 해결할 수 있음을 증명하여 기존 압축되지 않은 트리 기반 알고리즘보다 효율성을 크게 향상시켰습니다.
Causal Graph Dynamics and Kan Extensions
이 논문은 범주론의 칸 확장을 활용하여 국소적, 동기적, 결정론적인 특성을 가진 인과 그래프 역학이 글로벌 변환의 범주에 속함을 증명하고, 이를 통해 단조 인과 그래프 역학의 보편성을 규명합니다.