yusuke1997/dblp-id-title huggingface dataset:
Strong Optimal Lower Bounds for Turing Machines that Accept Nonregular Languages
Efficient Computations over Encrypted Data Blocks
Faster Monte-Carlo Algorithms for Fixation Probability of the Moran Process on Undirected Graphs
Towards a Formal Definition of the Control in Structured Programs
Bounded Degree Nonnegative Counting CSP
Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
The k-section of Treewidth Restricted Graphs
Logic of Predicates with Explicit Substitutions
A Linear Time Algorithm for the k Maximal Sums Problem
Equations in Transfinite Strings
Regular Chain Code Picture Languages of Nonlinear Descriptional Complexity
Dyck Language D 2 Is Not Absolutely Parallel
How To Be Fickle
How to Pack Your Items When You Have to Buy Your Knapsack
An Improved Algorithm for the Membership Problem for Extended Regular Expressions
Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
Ensuring Correctness by Arbitrary Postfixed-Points
Locally Chain-Parsable Languages
Verifying Single and Multi-mutator Garbage Collectors with Owicki-Gries in Isabelle/HOL
Automata That Take Advice
The Quantum Monad on Relational Structures
A Completeness Theorem fro Nondeterministic Kleene Algebras
On the Reachability Problem for Two-Dimensional Branching VASS
Quality Criteria for Partial Order Semantics of Place/Transition-Nets
An Invitation to Play
Positive Applications of Lattices to Cryptography
Mathematical Foundations of Computer Science 1988, MFCS'88, Carlsbad, Czechoslovakia, August 29 - September 2, 1988, Proceedings
Synchronizing Data Words for Register Automata
New Races in Parameterized Algorithmics
Arithmetic Constant-Depth Circuit Complexity Classes
Fine-Grained Complexity of Rainbow Coloring and its Variants
Between Min Cut and Graph Bisection
Learning in Knowledge Based System, a Possibilistic Approach
Breaking the Barrier 2^k for Subset Feedback Vertex Set in Chordal Graphs
A Fast Non-Commutative Algorithm for Matrix Multiplication
A Characterization of Abstract Families of Algebraic Power Series
On the Construction of Effective Random Sets
Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming
Probabilistic Input-Driven Pushdown Automata
The Lempel-Ziv Complexity of Fixed Points of Morphisms
From Dynamic Algebras to Test Algebras
On the Nature of TELLUS (a Typed Equational Logic Look over Uniform Specification)
On the Approximability of Minimum Topic Connected Overlay and Its Special Instances
Analysing Spatial Properties on Neighbourhood Spaces
Combinatorial Problems III. Degrees of Combinatorial Problems of Computing Machines
Multi-Party Protocols, Information Complexity and Privacy
The Transformational Machine: Theme and Variations
Binary Decision Diagrams by Shard Rewriting
A Uniform Approach to Inductive Posets and Inductive Closure
Formal Description of Programming Concepts: A Software Engineering Viewpoint
Algorithms and Complexity for Path Covers of Temporal DAGs
Kins of Context-Free Languages
Building Large k-Cores from Sparse Graphs
Computing Large Polynomial Powers Very Fast in Parallel
MSO Definable Text Languages
Syntactic Theories
Parameterized Spanning Tree Congestion
An Expressive Temporal Logic for Real Time
Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers
On the Equational Definition of the Least Prefixed Point
Computation of Least Fixed Points
Transition Graphs of Rewriting Systems over Unranked Trees
A Decomposition Theorem for Finite-Valued Tranducers and an Application to the Equivalence Problem
Proceedings of the MFCS '98 Workshop on Concurrency, Brno, Czech Republic, August 27-29, 1998
Finding a Highly Connected Steiner Subgraph and its Applications
Testing Simon's congruence
Expressiveness of Updatable Timed Automata
The Perfect Matching Reconfiguration Problem
Symmetry Classes of Hamiltonian Cycles
Comparison Between the Complexity of a Function and the Complexity of Its Graph
Parallel Knock-Out Schemes in Networks
Inductive Counting Below LOGSPACE
On the Role of Time and Space in Neural Computation
Concepts of Net Theory
Isomorphic Implication
Genericity and Measure for Exponential Time
Listing Subgraphs by Cartesian Decomposition
Hardness of Classically Simulating Quantum Circuits with Unbounded Toffoli and Fan-Out Gates
The Axiomatization Problem of a Theory of Linear Languages
Counting the Number of Solutions
The Bisection Problem for Graphs of Degree 4 (Configuring Transputer Systems)
Congestion Games and Coordination Mechanisms
Preprocessing Under Uncertainty: Matroid Intersection
Hypergraph Traversal Revisited: Cost Measures and Dynamic Algorithms
An Explicit Lower Bound of 5n - o(n) for Boolean Circuits
Clausal Resolution for CTL *
A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract)
Global Development via Local Observational Construction Steps
Trading Determinism for Time in Space Bounded Computations
Assertion Programming
A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors
A Topological Generalization of Propositional Linear Time Temporal Logic
Basic Mereology with Equivalence Relations
On a Mereological System for Relational Software Specifications
On Correctness and Essentiality of Some Ianov Schemas Equivalence Relations
Regular Model Checking for Systems with Effectively Regular Reachability Relation
Counting Distinct Square Substrings in Sublinear Time
Sublinear Ambiguity
A Taste of Linear Logic
Passive and Active Rules in Deductive Databases
Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach
Randomized Algorithms for Determining the Majority on Graphs
Finite Automaton from a Flowchart Scheme Point of View
Completeness in Differential Approximation Classes
How Good Is the Adversary Lower Bound?
Power from Power Series
An Iterative Approach for Counting Reduced Ordered Binary Decision Diagrams
Between Tree Patterns and Conjunctive Queries: Is There Tractability beyond Acyclicity?
Non-Determinism in Lindenmayer Systems and Global Transformations
Algebraic Methods in the Compositional Analysis of Logic Programs
Bin Packing Games with Selfish Items
The Centers of Context-Sensitive Languages
Complexity of Restricted Variants of Skolem and Related Problems
Infinite Synchronizing Words for Probabilistic Automata
The Complexity of Reachability Problems in Strongly Connected Finite Automata
Flexible Bandwidth Assignment with Application to Optical Networks - (Extended Abstract)
Smoothed Complexity Theory
Generalized Probabilistic Grammars
Graph Reducibility of Term Rewriting Systems
On the Skolem Problem for Reversible Sequences
Alternation Trading Proofs and Their Limitations
On the Complexity of the l-diversity Problem
Quantified Mu-Calculus for Control Synthesis
The Power of Two Prices: Beyond Cross-Monotonicity
Small Complexity Classes for Computable Analysis
On Existence of Complete Predicate Calculus in Metamathematics without Exponentiation
Faster FPT Algorithm for 5-Path Vertex Cover
Membership Problem in GL(2, Z) Extended by Singular Matrices
On the Complexity of Branching Games with Regular Conditions
Undecidable Problems for Probabilistic Network Programming
ℋ-Clique-Width and a Hereditary Analogue of Product Structure
Parameterized Complexity of Feature Selection for Categorical Data Clustering
State Complexity of Operations on Input-Driven Pushdown Automata
Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines (Extended Abstract)
Minimal and Monotone Minimal Perfect Hash Functions
Tight Algorithmic Applications of Clique-Width Generalizations
On Randomized Generation of Slowly Synchronizing Automata
Relativized Obliviousness
Algebra and Logic in Theoretical Computer Science
On Tinhofer's Linear Programming Approach to Isomorphism Testing
On the Structure of the Simulation Order of Proof Systems
Verifying Concurrent System Specification in COSY
Characterizations of Catalytic Membrane Computing Systems
Identification of Formal Languages
A Representation Theorem for Lambda Abstraction Algebras
Admissible Strategies in Infinite Games over Graphs
Eco-Grammar Systems, Decidability and the Tiling Problem
Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems
Gödel Numberings, Principal Morphisms, Combinatory Algebras: A Category-theoretic Characterization of Functional Completeness
Geometric Location Problems and Their Complexity
A Polynomial Kernel for 3-Leaf Power Deletion
Cannonizing Reducibility Method in the Theory of Program Schemata
Characterization of Context-Free Languages by Erasing Automata
Read-Write Causality
Topological Influence and Locality in Swap Schelling Games
Regional Languages and Tiling: A Unifying Approach to Picture Grammars
On the Conjugation of Standard Morphisms
Undecidable Problems Concerning Generalized Pascal Triangles of Commutative Algebras
Ambiguity Hierarchy of Regular Infinite Tree Languages
On the Parameterized Complexity of Deletion to ℋ-Free Strong Components
On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape
Finite Model Theory on Tame Classes of Structures
The Online Simple Knapsack Problem with Reservation and Removability
On Positivity and Minimality for Second-Order Holonomic Sequences
Morphisms and BWT-Run Sensitivity
Functional Programming and Combinatory Algebras
(Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata
The Canadian Traveller Problem on Outerplanar Graphs
On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph
On Pseudovarieties of Semiring Homomorphisms
Applied Algorithmic Logic
An Improved FPT Algorithm for the Flip Distance Problem
Solving Cheap Graph Problems an Meshes
The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains
Strong Inapproximability of the Shortest Reset Word
Inductive Continuity via Brouwer Trees
Different Modifications of Pointer Machines and Their Computational Power
Lower Bounds for the Product of Time and Space Requirements of Turing Machine Computations
Optimal Gossiping in Directed Geometric Radio Networks in Presence of Dynamical Faults
Semi-Commutation and Deterministic Petri Nets
Arithmetic Branching Programs with Memory
Complexity and Limiting Ratio of Boolean Functions over Implication
Full Abstraction for a Simple Parallel Programming Language
Analytic Tableaux for Finite and Infinite Post Logics
Monadic Second Order Logic on Graphs with Local Cardinality Constraints
Removing Bidirectionality from Nondeterministic Finite Automata
Scheduling and Traffic Allocation for Tasks with Bounded Splittability
Quantum Algorithms for Hopcroft's Problem
Axiomatizing Fully Complete Models for ML Polymorphic Types
A Shift-Invariant Metric on S zz Inducing a Non-trivial Tolology
Tractability of Packing Vertex-Disjoint A-Paths Under Length Constraints
Improved Parameterized Algorithms for Planar Dominating Set
Properties Complementary to Program Self-reference
Monadic Second-Order Logic with Arbitrary Monadic Predicates
On the Hardness of Compressing Weights
Mathematical Foundations of Computer Science 2003, 28th International Symposium, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003, Proceedings
A Formal Semantics of Influence in Bayesian Reasoning
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
Packing Arc-Disjoint Cycles in Tournaments
Reconfiguring Independent Sets on Interval Graphs
Measure on P: Robustness of the Notion
A Lattice-Theoretical Approach to Problem-Solving
Extending Partial Representations of Circle Graphs in Near-Linear Time
Effective Continued Fraction Dimension Versus Effective Hausdorff Dimension of Reals
Probabilistic Finite Automaton Emptiness Is Undecidable for a Fixed Automaton
The Degree Structure of 1-L Reductions
The Complexity of Membership Problems for Circuits over Sets of Integers
Quantitative Monoidal Algebra: Axiomatising Distance with String Diagrams
Colonies - A Theory of Reactive Agents (Preliminary Survey)
Tight Bounds for Deterministic h-Shot Broadcast in Ad-Hoc Directed Radio Networks
Sensitivity Lower Bounds from Linear Dependencies
Submodularity on a Tree: Unifying $L^\natural$ -Convex and Bisubmodular Functions
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
Generic Algorithms for the Generation of Combinatorial Objects
A Complete Axiomatic System for a Process-Based Spatial Logic
Cover Results and Normal Forms
A Complexity Approach to Tree Algebras: the Polynomial Case
An Improved Disjunctive Strictness Analysis for Lazy Functional Languages
Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond
Monadic Datalog and Regular Tree Pattern Queries
New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling
A Parallelization of Dijkstra's Shortest Path Algorithm
Fast Algorithms with Algebraic Monge Properties
Ehrenfeucht Test Set Theorem and Hilbert Basis Theorem: A Constructive Glimpse
Shape Recognition by a Finite Automaton Robot
The Join Levels of the Trotter-Weil Hierarchy Are Decidable
NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs
Abstract Numeration Systems and Tilings
Counting Classes and the Fine Structure between NC 1 and L
On Matroid Representability and Minor Problems
An Algorithm Constructing the Semilinear Post * for 2-Dim Reset/Transfer VASS
Machines that Can Output Empty Words
Token Sliding Reconfiguration on DAGs
Prime Languages
Recontamination Helps a Lot to Hunt a Rabbit
Mathematical Foundations of Computer Science 1976, 5th Symposium, Gdansk, Poland, September 6-10, 1976, Proceedings
A Direct Translation from LTL with Past to Deterministic Rabin Automata
On the Power of Synchronization in Parallel Computations
Probabilistic and Nondeterministic Unary Automata
A General Framework for Comparing Sequential and Parallel Rewriting
Gentzen Type Axiomatizations for PAL
A Proof of Shur's Conjecture on the Growth of Power-Free Languages over Large Alphabets
Relational Structures and Dynamics of Certain Discrete Systems
An Improved Approximation Scheme for Variable-Sized Bin Packing
Inferring a Tree from Walks
Robust Inference and Local Algorithms
Specifying Computations Using Hyper Transition Systems
Being Even Slightly Shallow Makes Life Hard
A Framework for Studying Grammars
Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds
Graph Decomposition for Improving Memoryless Periodic Exploration
Graph Exploration by a Finite Automaton
Membership Problems in Finite Groups
Improved Lower Bounds on the Number of Multiplications/Divisions Which Are Necessary to Evaluate Polynomials
Poset Properties of Complex Traces
Which Graph Motif Parameters Count?
Model Checking and Higher-Order Recursion
On the Coalgebra of Partial Differential Equations
On the Expressive Power of Quasiperiodic SFT
Asymptotically Efficient In-Place Merging
Alternating Parity Krivine Automata
Periodicity and Transitivity for Cellular Automata in Besicovitch Topologies
Decomposable Structures, Boolean Function Representations, and Optimization
On Some Properties of Cyclic Automata and Their Extensions
On Comparing Sums of Square Roots of Small Integers
Systolic Automata - Power, Characterizations, Nonhomogeneity
Randomness for Free
Linear High-Order Deterministic Tree Transducers with Regular Look-Ahead
#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank
Hypertree Decompositions: A Survey
Finite Automata Acceptation of Infinite Sequences
Resolution Proofs, Exponential Bounds, and Kolmogorov Complexity
Reducing AC-Termination to Termination
Filter Models for a Parallel and Non Deterministic Lambda-Calculus
Bottom-Up-Heap Sort, a New Variant of Heap Sort Beating on Average Quick Sort (if n is not very small)
Advice Complexity of the Online Induced Subgraph Problem
Hyper-minimisation Made Efficient
Scheduling Real-Time Mixed-Criticality Jobs
Structural Parameterizations of Clique Coloring
Two Lower Bounds for Circuits over the Basis (&, V, -)
In-Place Binary Counters
On the Complexity of Scheduling Incompatible Jobs with Unit-Times
Query Languages which Express all PTIME Queries for Trees and Unicyclic Graphs
P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
Complexity of the Cluster Vertex Deletion Problem on H-Free Graphs
Approximation Algorithms and Complexity Results for Path Problems in Trees of Rings
On the Representation of Kleene Algebras with Tests
On Some Discrete Optimization Problems in Mass Storage Systems
Largest Weight Common Subtree Embeddings with Distance Penalties
Some Recent Progress in Algorithmic Randomness
New Proofs for Jump DPDA's
Specification and Automatic Verification of Computational Reductions
Feature Constraints with First-Class Features
Team Semantics for the Specification and Verification of Hyperproperties
The Complexity of Interval Routing on Random Graphs
Regularity Problems for Weak Pushdown ω-Automata and Games
Give Me Some Slack: Efficient Network Measurements
Complexity of Preimage Problems for Deterministic Finite Automata
On Two Stronger Versions of Dejean's Conjecture
Computational Aspects of Disjunctive Sequences
Reducing Graph Transversals via Edge Contractions
Temporal Graph Realization with Bounded Stretch
Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs
Ideal Membership Problem for Boolean Minority and Dual Discriminator
Some Results Concerning 2-D On-line Tessellation Acceptors and 2-D Alternating Finite Automata
Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?
Determinacy and Rewriting of Top-Down and MSO Tree Transformations
Densest Subgraph in Dynamic Graph Streams
Accessibility in Automata on Scattered Linear Orderings
Hardness Results for Consensus-Halving
Small Universal One-State Linear Operator Algorithm
The Combinatorial Complexity of a Finite String
An Approximation Algorithm for the Matrix Tree Multiplication Problem
Compositional Proofs by Partial Specification of Processes
A Coloring Algorithm for Interval Graphs
Elimination Distance to Bounded Degree on Planar Graphs
Generalized Completion Problems with Forbidden Tournaments
Subcoloring of (Unit) Disk Graphs
Degrees of Parallelism in Computations
The Synchronization Problem for Locally Strongly Transitive Automata
Linear Time Temporal Logics over Mazurkiewicz Traces
On the Computational Complexity of Conservative Computing
Event Structures, Causal Trees, and Refinements
Quasipolynomial-Time Deterministic Kernelization and (Gammoid) Representation
Isomorphic Representation of Automata
Semantic and Syntactic Approaches to Simulation Relations
Match-Bounded String Rewriting Systems
Parameterized Algorithms for Module Motif
Language-Based Security
Data Encapsulation and Modularity: Three Views of Inheritance
Modular Constructions of Distributing Automata
The Cost of Stability in Network Flow Games
On the Decidability of Bounded Valuedness for Transducers
Constrained Minimum Enclosing Circle with Center on a Query Line Segment
Type Reconstruction for Functional Programs with Subtyping over a Lattice of Atomic Types
(poly(log log n), poly(log log n))-Restricted Verifiers are Unlikely to Exist for Languages in NP
Theory of Relations for Databases - A Tutorial Survey
AL-Khowarizmi: A Formal System for Higher-Order Logic Programming
Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31 - September 4, 1981, Proceedings
On Range Searching with Semialgebraic Sets
On Vanishing Sums of Roots of Unity in Polynomial Calculus and Sum-Of-Squares
On the Expressivity of Linear Recursion Schemes
Extraction and Implication of Path Constraints
Minimal Nontrivial Space Complexity of Probabilistic One-Way Turing Machines
Combinatorial Properties and Recognition of Unit Square Visibility Graphs
Multi-Head Finite Automata: Data-Independent Versus Data-Dependent Computations
Characterization of Programs and Their Synthesis from a Formalized Theory
Real Time Computations with Restrictions on Tape Alphabet
Combinatorial Games with Exponential Space Complete Decision Problems
On Equivalence of Programs
Isometric Path Complexity of Graphs
Homomorphic Realizations of Automata with Compositions
Greibach Normal Form Complexity
Faster Coupon Collecting via Replication with Applications in Gossiping
New Lower Bounds and Upper Bounds for Listing Avoidable Vertices
Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification
An O(n² log log log n) Expected Time Algorithm for the all Shortest Distance Problem
Probabilistic Automata and Probabilistic Logic
The Lower Reaches of Circuit Uniformity
Resolving Nondeterminism with Randomness
The Enumerability of P Collapses P to NC
Spatial and Temporal Refinement of Typed Graph Transformation Systems
Online Knapsack Problems with Estimates
Time Complexity of Constraint Satisfaction via Universal Algebra
Classically Simulating Quantum Circuits with Local Depolarizing Noise
The Second Calculus of Binary Relations
Structural Properties of Petri Nets
Isometric-Universal Graphs for Trees
Abstract Data Types in Computer Algebra
Analysis of the Non-Context-Free Component of Formal Languages
Periodicity and Immortality in Reversible Computing
Process Algebraic Frameworks for the Specification and Analysis of Cryptographic Protocols
The k-Median Problem for Directed Trees
Separating the Notions of Self- and Autoreducibility
Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs
Faster Approximation Schemes and Parameterized Algorithms on H -Minor-Free and Odd-Minor-Free Graphs
Fast Probabilistic Algorithms
The Complexity of Symmetric Functions in Parity Normal Forms
On the Performance of Mildly Greedy Players in k-Coloring Games
Characterization of Context-Free Languages with Polynomially Bounded Ambiguity
Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees
State Space Reduction Using Partial tau-Confluence
On Finding the Optimal Access Path to Resolve a Relational Data Base Query
Decomposition Methods and Sampling Circuits in the Cartesian Lattice
Faster Algorithms for k -Medians in Trees
Van Wijngaarden Grammars as a Special Information Processing Model
Object Oriented Application Flow Graphs and their Semantics
Proving Correctness of Constructor Implementations
Two-Level Contextual Grammars: The Internal Case
An Axiomatic Approach to Information Structures
Logical and Structural Approaches to the Graph Isomorphism Problem
Fully Dynamic Data Structure for LCE Queries in Compressed Space
On Probabilistic Quantified Satisfability Games
Real-Time Generation of Primes by a One-Dimensional Cellular Automaton with 11 States
Randomness and Reducibility
Dynamic Theories of Real and Complex Numbers
Symbolic Lookaheads for Bottom-up Parsing
Factorizations, Congruences, and the Decomposition of Automata and Systems
Sparse Sets, Tally Sets, and Polynomial Reducibilities
Random Deterministic Automata
A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
A New Type of Models of Computation
Compression of Clustered Inverted Files
Height-Deterministic Pushdown Automata
Zero Knowledge and Circuit Minimization
New Polynomial Cases of the Weighted Efficient Domination Problem
An Extensional Partial Combinatory Algebra Based on Lamda-Terms
Average-Case Intractability vs. Worst-Case Intractability
On the Complexity of Equivalent Transformations in Programming Languages
Refined Bounds on the Complexity of Sorting and Selection in D-Dimensional Space
Constructive Category Theory (No. 1)
One Guess One-Way Cellular Arrays
Negative Results on the Size of Deterministic Right Parsers
Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups
Interactive Computations of Optimal Solutions
The Data Complexity of MDatalog in Basic Modal Logics
The Maximum Independent Set Problem in Planar Graphs
The Simplest Non-Regular Deterministic Context-Free Language
The Metric Properties on the Semigroups and the Languages