yusuke1997/dblp-id-title huggingface dataset:
Probabilistic Automata Complexity of Languages Depends on Language Structure and Error Probability
Knot Theory, Jones Polynomial and Quantum Computing
Stabilization Bounds for Influence Propagation from a Random Initial State
A Family of Algebraic Systems Related to the Theory of Equations on Free Monoids
Graph-Theoretic Arguments in Low-Level Complexity
Improved Parameterized Upper Bounds for Vertex Cover
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
Unification in Incompletely Specified Theories: A Case Study
On NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems
Automatic Graphs and Graph D 0 L -Systems
Short Definitions in Constraint Languages
Quantifier Rank for Parity of Embedded Finite Models
Order Reconfiguration Under Width Constraints
From lambda-Calculus to Universal Algebra and Back
Streaming Word Problems
Some Connections between Representability of Complexity Classes and the Power of Formal Systems of Reasoning
Recognizable Sets with Multiplicities in the Tropical Semiring
The Problem of Reachability and Verification of Programs
Schemes with Recursion on Higher Types
Balanced Queries: Divide and Conquer
Some Theoretical Aspects of Applicative Multiprocessing
Computing with Large Populations Using Interactions
Outline of an Algebraic Language Theory
MaxCut Above Guarantee
Inductive Inference of Recursive Functions
Additive Cellular Automata over Z p and the Bottom of (CA, <=)
Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
Partial Information and Special Case Algorithms
Controlling Behaviours of Systems: Some Basic Concepts and some Applications
The Complexity of Simplifying ω-Automata Through the Alternating Cycle Decomposition
Finding Best Swap Edges Minimizing the Routing Cost of a Spanning Tree
Separating, Strongly Separating, and Collapsing Relativized Complexity Classes
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
Single-Path Petri Nets
A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms
Partial-Observation Stochastic Reachability and Parity Games
Learning Bayesian Networks Does Not Have to Be NP-Hard
The Offline Carpool Problem Revisited
Generalizations of Petri Nets
Rabin Tree Automata and Finite Monoids
Tangles and Single Linkage Hierarchical Clustering
Towards Algorithmic Explanation of Mind Evolution and Functioning
The Parallel Complexity of Deadlock Detection
Contribution to the Theory of Concurrency in Databases
Speed-Up Theorem Without Tape Compression
An Exact Algorithm for Knot-Free Vertex Deletion
On the Languages of Bounded Petri Nets
On Beta-Shifts Having Arithmetical Languages
The Complexity of Rerouting Shortest Paths
Definability by Weakly Deterministic Regular Expressions with Counters is Decidable
Simultaneous Multiparty Communication Protocols for Composed Functions
Speedup of Recognizable Trace Languages
Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs
Lower Bounds for Polygon Simplicity Testing and Other Problems
Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth
Edge Separators for Planar Graphs and Their Applications
Rational Graphs Trace Context-Sensitive Languages
Decidability of Trajectory-Based Equations
On Dynamic Graphs (Invited Talk)
Logic and Branching Automata
On Line-Separable Weighted Unit-Disk Coverage and Related Problems
Generalised Integer Programming Based on Logically Defined Relations
On Reducibility and Symmetry of Disjoint NP-Pairs
Faster Algorithms for Mean-Payoff Parity Games
Linear Dynamic Kahn Networks Are Deterministic
Extensions and Implementations of Abstract Data Type Specifications
On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges
Weights of Exact Threshold Functions
The Maximum Solution Problem on Graphs
Determining Processes by Violations
A Uniform Independence of Invariant Sentences
Alternating and Empty Alternating Auxiliary Stack Automata
Space Hierarchy Theorem Revised
Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon
Algebraic Graph Algorithms
Two Characterizations of the Logarithmic Alternation Hierarchy
Solving Visibility Problems by Using Skeleton Structures
Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
Better Bounds for Online Line Chasing
49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, Bratislava, Slovakia, August 26-30, 2024
Rational Transductions and Complexity of Counting Problems
A Toolkit for Proving Limitations of the Expressive Power of Logics
Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs
Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
Minimal Phylogenetic Supertrees and Local Consensus Trees
Dynamic Time Warping-Based Proximity Problems
Dataflow Semantics for Petri Nets
Mathematical Foundations of Computer Science 1979, Proceedings, 8th Symposium, Olomouc, Czechoslovakia, September 3-7, 1979
Mobility in the CC-Paradigm
On the Set of All Automata with the Same Monoid of Endomorphisms
On Divergence and Halting Problems for Monadic Program Schemas
Post Correspondence Problem: Primitivity and Interrelations with Complexity Classes
Infinite Normal Forms for Non-Linear Term Rewriting Systems
Pushing for Weighted Tree Automata
Codings of Nonnegative Integers
Insertion and Deletion of Words: Determinism and Reversibility
An Improved Claw Finding Algorithm Using Quantum Walk
A 3-Approximation Algorithm for Movement Minimization in Conveyor Flow Shop Processing
Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms
Parameterized Complexity of Fair Vertex Evaluation Problems
Rewrite Orderings and Termination of Rewrite Systems
Complexity of Generalized Graph Coloring
Symmetric Proofs in the Ideal Proof System
47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, Vienna, Austria, August 22-26, 2022
Unordered Constraint Satisfaction Games
On Polynomial-Time Decidability of k-Negations Fragments of FO Theories (Extended Abstract)
Tarskian Set Constraints Are in NEXPTIME
Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
Probabilistic Two-Way Machines
Developing Implicit Data Structures
A Family of NFA's Which Need 2 n - alpha Deterministic States
A Generalization of Scott's Flow Diagrams
46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, Tallinn, Estonia, August 23-27, 2021
Real Interactive Proofs for VPSPACE
A Case Study of Genome Evolution: From Continuous to Discrete Time Model
An Application of the Theory of Free Partially Commutative Monoids: Asymptotic Densities of Trace Languages
When Are Prime Formulae Characteristic?
On Some Formal Grammars Generating Dependency Trees
Bridging Across the log(n) Space Frontier
Taking It to the Limit: Approximate Reasoning for Markov Processes
A BDD-Representation for the Logic of Equality and Uninterpreted Functions
A Model for Real-Time Systems
Dynamic Hashing Strategies
Games with ω-Automatic Preference Relations
Minimal Indices for Successor Search - (Extended Abstract)
Bringing Order to Special Cases of Klee's Measure Problem
Finite State Transducers for Modular Möbius Number Systems
Knocking Out P k -free Graphs
Finitary Semantics of Linear Logic and Higher-Order Model-Checking
Defining Languages by Mazurkiewicz Algorithms
Two Results about Quantum Messages
Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats Lenstra
The Generalised Colouring Numbers on Classes of Bounded Expansion
Coherent Control and Distinguishability of Quantum Channels via PBS-Diagrams
Longest Gapped Repeats and Palindromes
Hierarchy of Monotonically Computable Real Numbers
On the Communication Complexity of Parallel Computation
Observable Properties of Higher Order Functions that Dynamically Create Local Names, or What's new?
Recognizing Graphs Close to Bipartite Graphs
Edge Coloring of Bipartite Graphs with Constraints
On Strict Interpretations of Grammar Forms
A dexptime-Complete Dolev-Yao Theory with Distributive Encryption
Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
Decidability of Monadic Theories
Measure Theoretic Completeness Notions for the Exponential Time Classes
Modal Inclusion Logic: Being Lax is Simpler than Being Strict
On the Herbrand Kleene Universe for Nondeterministic Computations
When Can an Equational Simple Graph Be Generated by Hyperedge Replacement?
On Some Types of Pseudo-Random Sequences
The Influence of the Machine Model on the Time Complexity of Context-Free Language Recognition
The Expressive Power of Intensional Logic in the Semantics of Programming Languages
Stochastic Data Streams
Two Decidability Results for Deterministic Pushdown Automata
Point-To-Set Principle and Constructive Dimension Faithfulness
Pumping Lemmas for Tree Languages Generated by Rewrite Systems
Almost Every Set in Exponential Time is P-Bi-Immune
Models of DNA Computation
Routing with Finite Speeds of Memory and Network
On Synthesis of Distributed Monitors (Invited Talk)
Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms
Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network
Robust Orale Machines
Implementation of Parallel Graph Reduction by Explicit Annotation and Program Transformation
Depth-3 Circuits for Inner Product
Balanced Paths in Colored Graphs
Approximate Graph Isomorphism
On the Complexity of Incremental Computation
Extending Temporal Logic by Explicit Concurrency
On Minimum Edge Ranking Spanning Trees
On the Quantifier-Free Dynamic Complexity of Reachability
Online Clustering with Variable Sized Clusters
On the Symmetries of and Equivalence Test for Design Polynomials
A Uniform Universal CREW PRAM
Proving Programs by Sets of Computations
Skolem Meets Schanuel
Preservation Theorems on Sparse Classes Revisited
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction
Admissible Representations of Effective CPO's
New Developments in Quantum Algorithms
Weakly-Synchronized Ground Tree Rewriting - (with Applications to Verifying Multithreaded Programs)
Optimal Bounds for Estimating Entropy with PMF Queries
Trustworthy Graph Algorithms (Invited Talk)
Towards a Calculus of Predicate Transformers
Learning Decision Lists from Noisy Examples
Sitting Closer to Friends Than Enemies, Revisited
A More Efficient Simulation Algorithm on Kripke Structures
Two Variables and Two Successors
Reoptimization of the Metric Deadline TSP
Reachability in Register Machines with Polynomial Updates
Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth
Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays
Top-down Analysis of Programming Languages without Backtrack (in Russian)
Linear-Time Computation of Local Periods
Graph Search Trees and the Intermezzo Problem
A Second-Order Pattern Matching Algorithm for the Cube of Typed Lambda-Calculi
Universality Frontier for Asynchronous Cellular Automata
Computational Processes Generated by Programs with Recursive Procedures and Block Structures
Independent Set Reconfiguration on Directed Graphs
Colouring H-Free Graphs of Bounded Diameter
Deterministic Behavioural Models for Concurrency
Spanning-Tree Games
On Determinism in Eco-Grammar Systems
Timed Network Games
Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order
Subword Complexity and Decomposition of the Set of Factors
Small Universal Minsky Machines
On the Approximability of the Steiner Tree Problem
Resolution Width and Cutting Plane Rank Are Incomparable
A Lower Bound on Complexity of Branching Programs (Extended Abstract)
On Factor Universality in Symbolic Spaces
Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I
How to Define Functionals of Free Structures in Typed Lambda Calculus
Partial Order Semantics and Read Arcs
New Results on Directed Edge Dominating Set
On Infinite Terms Having a Decidable Monadic Theory
Lexicographic Transductions of Finite Words
Wait-Only Broadcast Protocols Are Easier to Verify
The Compositional Structure of Bayesian Inference
Approximating Weak Bisimulation on Basic Process Algebras
A Note on Improving Input Strings for Paging Machines
Constructions of Grammars for Formal Languages
Classes of Structurally Isomorphic {NP}-Optimization Problems
An Improved Approximation Bound for Spanning Star Forest and Color Saving
Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities
The Direct Product of Automata and Quasi-Automata
System Simulation and the Sensitivity of Self-Stabilization
A Linear-Time Nominal μ-Calculus with Name Allocation
Support Size Estimation: The Power of Conditioning
On the Synthesis of Automata with Several Initial States
Programming Biomolecules That Fold Greedily During Transcription
Computation and Deduction
On the Complexity of Recognizing the Hilbert Basis of a Linear Diophantine System
L-Systems: A Device in Biologically Motivated Automata Theory
An Elementary Proof of a 3n - o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
One-Sided Dyck Reduction Over Two Letter Alphabet and Deterministic Context-Free Languages
A Parameterized Complexity Analysis of Combinatorial Feature Selection Problems
The Connection between Modal Logic and Algorithmic Logic
On the Equivalence of Planar Grammars and Parallel Picture Processing Algorithms
The Strength of Non-size-increasing Computation (Introduction and Summary)
On the Complexity of Word Problems in Certain Thue Systems (Preliminary Report)
A Functorial Semantics for Observed Concurrency
Error Detection Using Regular Languages
Online Sum-Radii Clustering
Probabilistic Secret Sharing
Design, Proof and Analysis of New Efficient Algorithms for Incremental Attribute Evaluation
Improved Time and Space Hierarchies of One-Tape Off-Line TMs
On Upper and Lower Bounds on the Length of Alternating Towers
On Atomic Nets and Concurrency Relations
The Bounded Search Tree Algorithm for the Closest String Problem Has Quadratic Smoothed Complexity
Dual VP Classes
Stretching by Probabilistic Tree Automata and Santos Grammars
Transducer-Based Rewriting Games for Active XML
A Constant Factor Approximation for the Generalized Assignment Problem with Minimum Quantities and Unit Size Items
Timed Bisimulation and Open Maps
Hammock-on-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest Paths and Other Problems
Binary Search in Graphs Revisited
Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality
Query Languages for Real Number Databases Based on Descriptive Complexity over R
Deciding Predicate Logical Theories Of Real-Valued Functions
Area Complexity of Merging
Solving Counter Parity Games
Fast Dynamic Weight Matchings in Convex Bipartite Graphs
Proof System for Weakest Prespecification and its Applications
Free Constructions in Algebraic Institutions
Locally Explicit Construction of Rödl's Asymptotically Good Packings
Algebraic Representations of Unique Bipartite Perfect Matching
FO Model Checking on Nested Pushdown Trees
On the Quasi-Controllability of Automata
Towards a Categorical Semantics Type Classes
Symmetric Functions Capture General Functions
Elimination Distance to Dominated Clusters
Word Structures and Their Automatic Presentations
Online and Dynamic Recognition of Squarefree Strings
On the General Chain Pair Simplification Problem
Cyclic Complexity of Words
Algebraic Theory of Module Specification with Constraints
A By-Level Analysis of Multiplicative Exponential Linear Logic
On Some Lattice-Theoretic Properties of Generable Languages
A Robust Class of Regular Languages
3-Dimensional Shortest Paths in the Presence of Polyhedral Obstacles
Football Elimination Is Hard to Decide Under the 3-Point-Rule
On the Propositional Algorithmic Logic
On the Strength of Temporal Proofs
An Improved Approximation Algorithm for the Traveling Tournament Problem with Maximum Trip Length Two
On Uniformization in the Full Binary Tree
Algebraic Recognizability of Languages
Eilenberg Theorems for Free
The LR(k) Parser
String-Matching in Real Time: Some Properties of the Data Structure
On the Computational Efficiency of Symmetric Neural Networks
Reconfiguration of Graph Minors
A Category of Transition Systems and Its Relations with Orthomodular Posets
Popular Matchings: Good, Bad, and Mixed (Invited Talk)
Iterated Length-Preserving Rational Transductions
Global Properties of 2D Cellular Automata: Some Complexity Results
A Pi-Calculus with Explicit Substitutions: the Late Semantics
Computability of Probabilistic Parameters for Some Classes of Formal Languages
Some Variants of the Star Height Problem
Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions
Solving Analytic Differential Equations in Polynomial Time over Unbounded Domains
Adversarial Models for Priority-Based Networks
On the Proof Method for Bisimulation (Extended Abstract)
Communication in Parallel Communicating Lindenmayer Systems (Extended Abstract)
Abelian Pattern Avoidance in Partial Words
Characterizing Regular Languages with Polynomial Densities
A Cubic Vertex-Kernel for Trivially Perfect Editing
Parsing as a Subtask of Compiling
Equivalence Notions for Concurrent Systems and Refinement of Actions (Extended Abstract)
Snake-Deterministic Tiling Systems
Car-Sharing between Two Locations: Online Scheduling with Two Servers
On the Complexity of Mixed Discriminants and Related Problems
Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets
Observing Localities (Extended Abstract)
Linear Problem Kernels for Planar Graph Problems with Small Distance Property
Expander Properties and the Cover Time of Random Intersection Graphs
Drawing Planar Graphs on Points Inside a Polygon
A Chomsky-Like Hierarchy of Infinite Graphs
An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
Semantics of CSP via Translation into CCS
Is Your Model Checker on Time? On the Complexity of Model Checking for Timed Modal Logics
On r-Simple k-Path
Average State Complexity of Operations on Unary Automata
Maintaining Proximity in Higher Dimensional Spaces
QMA with Subset State Witnesses
Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity
On Specfic Features of Recognizable Families of Languages
Network-Based Dissolution
And/Or Hierarchies and Round Abstraction
On the Use of Guards for Logics with Data
Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities
Nondeterminism Is Essential for Two-Way Counter Machines
Abstract Syntax and Variable Binding for Linear Binders
Deterministic Models of Communication Faults
On the Comparison of Notions of Approximation
Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization
Some Properties of Limit Recursive Functions
First-Fit Coloring of Forests in Random Arrival Model
Probabilistic Concurrent Constraint Programming: Towards a Fully Abstract Model
Iterative Systems of Equations
Object Interaction
Approximation Algorithms for the Maximum Internal Spanning Tree Problem
Composition of Two Semi Commutations
Layered Fan-Planar Graph Drawings
Model Checking Real-Time Properties of Symmetric Systems
On Planar Valued CSPs
Proof-Theoretic Characterisations of Logic Programs
Frame Definability for Classes of Trees in the µ -calculus
Two Pebbles Don't Suffice
Combinatorial Hardness Proofs for Polynomial Evaluation
Multiway Cuts with a Choice of Representatives
Another Approach for Proving Program Correctness
On Pebble Automata for Data Languages with Decidable Emptiness Problem
Monotone Switching Circuits and Boolean Matrix Product
Languages Over Free Groups
Partial Interpretations of Higher Order Algebraic Types (Extended Abstract)
Efficient Enumerations for Minimal Multicuts and Multiway Cuts
A Greedy Algorithm for Constructing Shortest Common Superstrings
Scheduling with Locality by Routing
Towards Efficient Reasoning Under Guarded-Based Disjunctive Existential Rules
On Piecewise Affine Reachability with Bellman Operators
Understanding Nets
Krenn-Gu Conjecture for Sparse Graphs
Simple Models for Recursive Schemes
Rewriting Guarded Negation Queries
Parameterized Max Min Feedback Vertex Set
Empty Alternation
Complexity of Decision Problems Under Incomplete Information
Reductions for Monotone Boolean Circuits
Parallel Enumeration of Parse Trees
Substring Languages
Vector Language: Simple Description of Hard Instances (Extended Abstract)
Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
An Iterative Metric Fully Abstract Semantics for Nondeterministic Dataflow (Extended Abstract)
Distributed Strategies Made Easy
On Models and Algebras for Concurrent Processes
Upper Bounds on the Bisection Width of 3- and 4-Regular Graphs
Timed Automata with Monotonic Activities
Relative Succinctness of Representations of Languages and Separation of Complexity Classes
Projection Theorems Using Effective Dimension
On Extended Boundary Sequences of Morphic and Sturmian Words
Punctual Presentability in Certain Classes of Algebraic Structures
A Logical Characterization of Timed (non-)Regular Languages
The Promise of Electronic Prototyping
Closure Properties of the Family of Languages Recognized by One-Way Two-Head Deterministic Finite State Automata
Minimal Obstructions to C₅-Coloring in Hereditary Graph Classes
Streaming Kernelization
How to Find Invariants for Coloured Petri Nets
Sharing One Secret vs. Sharing Many Secrets: Tight Bounds for the Max Improvement Ratio
New Results on Completeness and Consistency of Abstract Data Types
Universal Lyndon Words
Fully Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata
Rabbits Approximate, Cows Compute Exactly!
Abstract Congruence Criteria for Weak Bisimilarity
Complexity of Counting First-Order Logic for the Subword Order
The Complexity of Quantified Constraints Using the Algebraic Formulation
Regular Collections of Message Sequence Charts
Capturing Complexity Classes with Lindström Quantifiers
Another Look at Parameterization Using Algebras with Subsorts
A Solution of the Complement Problem in Associative-Commutative Theories
Approximability of Bounded Occurrence Max Ones
Computing epsilon-Free NFA from Regular Expressions in O(n log²(n)) Time
Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams
The Shortest Identities for Max-Plus Automata with Two States
Unique Fixed Point Induction for McCarthy's Amb
Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
On the Complexity of Inductive Inference (Preliminary Report)
Polymorphic Subtyping Without Distributivity
Two Dimensional Packing: The Power of Rotation
On Relaxation Rules in Algorithmic Logic
Pinwheel Scheduling With Tow Distinct Numbers
Compositional Weak Metrics for Group Key Update
The Approximation Problem in Computational Statistics
A Mathematical Model of Parallel Information Processing
The Complexity of Satisfiability for Fragments of Hybrid Logic-Part I
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
A Dynamic Algorithm for Reachability Games Played on Trees
Toward the Eigenvalue Power Law
The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs
The Height of Factorization Forests
Reachability in Higher-Order-Counters
Bounded Recursion and Complexity Classes
Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach
Exact Algorithms for L (2, 1)-Labeling of Graphs
Non-Axiomatizability of the Equational Theories of Positive Relation Algebras (Invited Talk)
Fine-Grained Complexity of Program Analysis (Invited Talk)
A Note on k-Colorability of P5-Free Graphs
Treewidth-Two Graphs as a Free Algebra
On the Minimization Prolem for Omega-Automata
Positive Recursive Type Assignment
Unary Prime Languages
Auctions for Partial Heterogeneous Preferences
On the Structure of the Monadic Logic of the Binary Tree