HIGHLIGHTS 2018: HIGHLIGHTS OF LOGIC, GAMES AND AUTOMATA

This page contains an index consisting of author-provided keywords.

A
abstract interpretation	Algorithms for inclusion into a regular language
Acceleration	Universal Safety for Timed Petri Nets is PSPACE-complete
admissible strategies	Beyond Admissibility: Rationality in Quantitative Games
Algebraic language theory	Eilenberg Theorems for Free Abstract MSO languages over monads
algorithmic complexity	Solving parity games in quasi-polynomial time -- a logician's approach
almost-sure	Reachability for Branching Concurrent Stochastic Games
alternating finite automata	The Linear Space Hypothesis and Its Close Connection to Two-Way Finite Automata
alternating-time temporal logic	Towards Partial Order Reductions for Strategic Ability
amalgamation	Decidability in data Petri nets — a conjecture.
AMBA AHB	Strix: Explicit Reactive Synthesis Strikes Back!
ambiguity	A Pattern Logic for Automata with Outputs
amortized analysis	Counting Triangles under Updates in Worst-Case Optimal Time
Analysis of probabilistic systems	Bisimilarity Distances for Approximate Differential Privacy
Aperiodic Sets	Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid
Approximation	Symbolic Approximation of Weighted Timed Games
arithmetic circuit complexity	Characterization of non-associative circuits using automata, and applications
asynchronous systems	Towards Partial Order Reductions for Strategic Ability
automata	Efficient and Modular Coalgebraic Partition-Refinement Regular and First Order List Functions Is your automaton good for playing games ?
automata over infinite alphabets	Polynomial-time equivalence testing for deterministic fresh-register automata
automata theory	Algorithms for inclusion into a regular language
automata with outputs	A Pattern Logic for Automata with Outputs
automated synthesis	Safe and Optimal Scheduling of Hard and Soft Tasks
Automatic verification	DEEPSEC: Deciding Equivalence Properties in Security Protocols Theory and Practice
automaton semigroups	A new hierarchy for automaton semigroups
B
beyond worst-case synthesis	Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes
Bisimilarity Distances	Bisimilarity Distances for Approximate Differential Privacy
bisimilarity minimization	Efficient and Modular Coalgebraic Partition-Refinement
bisimilarity testing	Polynomial-time equivalence testing for deterministic fresh-register automata
Bisimulation	Bisimilarity Distances for Approximate Differential Privacy
Borel probability measure	On Computing the Measures of First-Order Definable Sets of Trees
bounded ambiguity	Pumping lemmas for weighted automata
branching automata	Logic and rational languages of scattered and countable series-parallel posets
branching processes	Reachability for Branching Concurrent Stochastic Games
Büchi	A unified approach to Büchi determinisation Is your automaton good for playing games ?
Büchi automata	Permutation Games for the Weakly Aconjunctive mu-Calculus
C
coalgebra	Efficient and Modular Coalgebraic Partition-Refinement
communicating finite-state machine	It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before"
Complement	The Containment Problem for Unambiguous Register Automata
complex changes	Reachability and Distances under Multiple Changes
complexity	Universal parity graphs and lower bounds for parity games DEEPSEC: Deciding Equivalence Properties in Security Protocols Theory and Practice Is your automaton good for playing games ?
complexity results	Constrained existence problem for weak subgame perfect equilibria with omega-regular Boolean objectives
Computational Complexity	Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
conditional value at risk	Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes
conjunctive queries	On Computing the Measures of First-Order Definable Sets of Trees
constant delay enumeration	Answering UCQs under updates
constraint problem	Constrained existence problem for weak subgame perfect equilibria with omega-regular Boolean objectives
containment	Resynchronizing Classes of Word Relations
Containment Problem	The Containment Problem for Unambiguous Register Automata
Continuous time	Continuous-Time Markov Decisions based on Partial Exploration
Controller Synthesis	Eventually safe languages and Good-for-Games automata
cost register automata	Weak Cost Register Automata are Still Powerful
counting complexity	Answering UCQs under updates
Coverability	Universal Safety for Timed Petri Nets is PSPACE-complete
coverability languages	Regular separability of WSTS
coverability problem	Decidability in data Petri nets — a conjecture.
covering problem	Pointlike sets for varieties determined by groups
cyclic order	Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms
D
data skew	Counting Triangles under Updates in Worst-Case Optimal Time
Data transducers	Automatic Synthesis of Systems with Data
Data words	Automatic Synthesis of Systems with Data
decision problem	A new hierarchy for automaton semigroups
decision problems	Unboundedness problems for languages of vector addition systems
descriptional complexity	Determinizing two-way automata with linear-time Turing machines
descriptive and computational complexity	On the First-Order Complexity of Subgraph Isomorphism
descriptive complexity	Solving parity games in quasi-polynomial time -- a logician's approach
determinisability	A Pattern Logic for Automata with Outputs
determinisation	A unified approach to Büchi determinisation
Deterministic Parity Automaton	Strix: Explicit Reactive Synthesis Strikes Back!
determinization methods	Permutation Games for the Weakly Aconjunctive mu-Calculus
diagonal constraints	Reachability in timed automata with diagonal constraints
Differential Privacy	Bisimilarity Distances for Approximate Differential Privacy
Diophantine Equations	Costs and Rewards in Priced Timed Automata
distances	Reachability and Distances under Multiple Changes
Distributed synthesis	Reasoning about Knowledge and Strategies
doubly exponential run	The Reachability Problem for Vector Addition Systems is Not Elementary
Duality	Eilenberg Theorems for Free
dynamic algorithms	Answering UCQs under updates
Dynamic binding	Bracket Algebras: a nominal theory of interleaved scopes
dynamic complexity	Reachability and Distances under Multiple Changes
E
Eilenberg theorem	Eilenberg Theorems for Free
elementary algorithms	An Optimal Construction for the Barthelmann-Schwentick Normal Form on Classes of Structures of Bounded Degree
ellipsoid method	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
entropy	A new hierarchy for automaton semigroups
Epistemic logics	Reasoning about Knowledge and Strategies
equivalence problem	Weak Cost Register Automata are Still Powerful
Equivalence properties	DEEPSEC: Deciding Equivalence Properties in Security Protocols Theory and Practice
equivalence testing	Polynomial-time equivalence testing for deterministic fresh-register automata
Existential monadic second order properties	Non-convergence in existential monadic second order logic of random graphs
expected shortfall	Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes
Expected stopping time	Graph Planning with Expected Finite Horizon
expected value	What can you expect of a weighted automaton?
F
Factorisation forest	A Ramsey Theorem for semigroups
finite automata	Determinizing two-way automata with linear-time Turing machines
Finite horizon	Graph Planning with Expected Finite Horizon
First order logic	Uniformization Problem for Variants of First Order Logic over Words
First order logic with counting	Distinguishing Graphs via Logics with Counting
first-order logic	An Optimal Construction for the Barthelmann-Schwentick Normal Form on Classes of Structures of Bounded Degree On Computing the Measures of First-Order Definable Sets of Trees On the First-Order Complexity of Subgraph Isomorphism It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before"
fixed dimension	The Reachability Problem for Vector Addition Systems is Not Elementary
fixed-point logic	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
fixpoints	Algorithms for inclusion into a regular language
Formal verification	Polynomial Vector Addition Systems With States
functionality	A Pattern Logic for Automata with Outputs
G
Game theory	Symbolic Approximation of Weighted Timed Games
games	Universal parity graphs and lower bounds for parity games Observation synthesis for games with imperfect information Is your automaton good for playing games ?
games on finite graphs	Beyond Admissibility: Rationality in Quantitative Games
GFG automata	Eventually safe languages and Good-for-Games automata
good expressions	Regular Transducer Expressions for Regular Transformations
graph isomorphism problem	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
Graph planning	Graph Planning with Expected Finite Horizon
graphs	Gralog, a visual tool for working with graphs, games, automata, logics
guarantees	Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes
H
happened-before relation	It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before"
hardness results	Reachability in timed automata with diagonal constraints
homogeneous structures	Decidability in data Petri nets — a conjecture.
I
Idempotent	A Ramsey Theorem for semigroups
Imperfect information	Reasoning about Knowledge and Strategies Observation synthesis for games with imperfect information
incremental view maintenance	Counting Triangles under Updates in Worst-Case Optimal Time
index hierarchy	Unambiguous languages exhaust the index hierarchy
Infinite Games	Synthesizing Optimally Resilient Controllers Parity Games with Weights
Infinite state system	Polynomial Vector Addition Systems With States
infinite trees	Unambiguous languages exhaust the index hierarchy
infinite words	A unified approach to Büchi determinisation
Interactive learning environment	Introduction to Iltis: An Interactive, Web-Based System for Teaching Logic
Interleaved scopes	Bracket Algebras: a nominal theory of interleaved scopes
K
Kantorovich Metric	Bisimilarity Distances for Approximate Differential Privacy
Kosaraju-Sullivan algorithm	Polynomial Vector Addition Systems With States
L
Labelled Markov Chains	Bisimilarity Distances for Approximate Differential Privacy
language inclusion	Algorithms for inclusion into a regular language
Language Inclusion Problem	The Containment Problem for Unambiguous Register Automata
limit-sure	Reachability for Branching Concurrent Stochastic Games
Linear algebra	Polynomial Vector Addition Systems With States
Linear Temporal Logic	Eventually safe languages and Good-for-Games automata Strix: Explicit Reactive Synthesis Strikes Back!
Linear time mu-calculus	Eventually safe languages and Good-for-Games automata
linear-time Turing machines	Determinizing two-way automata with linear-time Turing machines
locality	An Optimal Construction for the Barthelmann-Schwentick Normal Form on Classes of Structures of Bounded Degree
logic	Regular and First Order List Functions A Pattern Logic for Automata with Outputs
Logical definability	Distinguishing Graphs via Logics with Counting
long run	The Reachability Problem for Vector Addition Systems is Not Elementary
lower bound	Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
lower bounds	An Optimal Construction for the Barthelmann-Schwentick Normal Form on Classes of Structures of Bounded Degree
M
m log n	Efficient and Modular Coalgebraic Partition-Refinement
markov chains	Efficient and Modular Coalgebraic Partition-Refinement
Markov decision process	Continuous-Time Markov Decisions based on Partial Exploration
Markov decision processes	Safe and Optimal Scheduling of Hard and Soft Tasks Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes
Mazurkiewicz traces	Towards Partial Order Reductions for Strategic Ability
Mealy automata	A new hierarchy for automaton semigroups
mean-payoff games	Solving mean-payoff parity games in pseudo-quasi-polynomial time.
Memory Requirements	Parity Games with Weights
message sequence chart	It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before"
modal logic	Permutation Games for the Weakly Aconjunctive mu-Calculus
modal mu	Solving parity games in quasi-polynomial time -- a logician's approach
model checking	Towards Partial Order Reductions for Strategic Ability
model-checking	A Pattern Logic for Automata with Outputs
Monad	Eilenberg Theorems for Free
Monadic second order logic	Abstract MSO languages over monads
Monads	Abstract MSO languages over monads
MSO	Logic and rational languages of scattered and countable series-parallel posets
MSO extension	Expressing Unboudedness in MSO + nabla
MSO Logic	Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid
mu-calculus	Permutation Games for the Weakly Aconjunctive mu-Calculus
multi-objective optimization	Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes
multi-objective reasoning	Safe and Optimal Scheduling of Hard and Soft Tasks
multiplayer games	Constrained existence problem for weak subgame perfect equilibria with omega-regular Boolean objectives
multiplicity tree automata	Characterization of non-associative circuits using automata, and applications
N
Nash equilibria	Reasoning about Knowledge and Strategies
NFA	A Pattern Logic for Automata with Outputs
NL optimization	The Linear Space Hypothesis and Its Close Connection to Two-Way Finite Automata
NL search	The Linear Space Hypothesis and Its Close Connection to Two-Way Finite Automata
Nominal sets	Bracket Algebras: a nominal theory of interleaved scopes
non-associative computations	Characterization of non-associative circuits using automata, and applications
normal form	An Optimal Construction for the Barthelmann-Schwentick Normal Form on Classes of Structures of Bounded Degree
O
omega automata	A unified approach to Büchi determinisation
omega-regular objectives	Constrained existence problem for weak subgame perfect equilibria with omega-regular Boolean objectives
on-the-fly solving	Permutation Games for the Weakly Aconjunctive mu-Calculus
optimality	Counting Triangles under Updates in Worst-Case Optimal Time
order problem	A new hierarchy for automaton semigroups
order theory	Beyond Admissibility: Rationality in Quantitative Games
P
Pareto Domination	Costs and Rewards in Priced Timed Automata
parity	Is your automaton good for playing games ?
parity automata	Permutation Games for the Weakly Aconjunctive mu-Calculus
Parity Game	Strix: Explicit Reactive Synthesis Strikes Back!
parity games	Solving parity games with tangles Permutation Games for the Weakly Aconjunctive mu-Calculus Universal parity graphs and lower bounds for parity games Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games Solving mean-payoff parity games in pseudo-quasi-polynomial time. Solving parity games in quasi-polynomial time -- a logician's approach Parity Games with Weights Unambiguous languages exhaust the index hierarchy
parity objectives	Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes
Partial exploration	Continuous-Time Markov Decisions based on Partial Exploration
partial order reduction	Towards Partial Order Reductions for Strategic Ability
Partially Lossy Queues	Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid
partition refinement	Efficient and Modular Coalgebraic Partition-Refinement
Petri nets	Decidability in data Petri nets — a conjecture. Regular separability of WSTS Universal Safety for Timed Petri Nets is PSPACE-complete
Petri nets with data	Decidability in data Petri nets — a conjecture.
pointlikes	Pointlike sets for varieties determined by groups
polynomial time	Reachability for Branching Concurrent Stochastic Games
Presburger arithmetic	Logic and rational languages of scattered and countable series-parallel posets
Priced Timed Automata	Costs and Rewards in Priced Timed Automata
probabilistic semantics	What can you expect of a weighted automaton?
probabilistic verification	Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes Continuous-Time Markov Decisions based on Partial Exploration
probability quantifier	Expressing Unboudedness in MSO + nabla
programming environment	Gralog, a visual tool for working with graphs, games, automata, logics
progress measure	Solving mean-payoff parity games in pseudo-quasi-polynomial time.
Propositional/modal/predicate logic	Introduction to Iltis: An Interactive, Web-Based System for Teaching Logic
pseudo-quasi polynomial algorithm	Solving mean-payoff parity games in pseudo-quasi-polynomial time.
Pumping Lemma	A Ramsey Theorem for semigroups Pumping lemmas for weighted automata
Q
Quantifier depth	Distinguishing Graphs via Logics with Counting
quantifier depth and variable width	On the First-Order Complexity of Subgraph Isomorphism
quantifier elimination	Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms
Quantitative Games	Parity Games with Weights
quantitative objectives	Beyond Admissibility: Rationality in Quantitative Games
quasipolynomial algorithm	Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
query evaluation	Answering UCQs under updates
R
Random graphs	Non-convergence in existential monadic second order logic of random graphs
Ranking Functions	Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
Rational Sets	Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid
reachability	Reachability for Branching Concurrent Stochastic Games Reachability and Distances under Multiple Changes
reachability algorithms	Reachability in timed automata with diagonal constraints
Reachability problem	Polynomial Vector Addition Systems With States
Reactive Synthesis	Strix: Explicit Reactive Synthesis Strikes Back!
Real-time systems	Symbolic Approximation of Weighted Timed Games
Recognizable languages	Abstract MSO languages over monads
Recognizable Sets	Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid
Register Automata	Polynomial-time equivalence testing for deterministic fresh-register automata The Containment Problem for Unambiguous Register Automata Automatic Synthesis of Systems with Data
regular languages	Determinizing two-way automata with linear-time Turing machines Bracket Algebras: a nominal theory of interleaved scopes On Computing the Measures of First-Order Definable Sets of Trees
regular separability	Regular separability of WSTS
regularity problem	Regular separability of WSTS
Reiterman theorem	Eilenberg Theorems for Free
Relational semantics	Bracket Algebras: a nominal theory of interleaved scopes
resynchronization	Resynchronizing Classes of Word Relations
Robustness	Synthesizing Optimally Resilient Controllers
S
Safety Checking	Universal Safety for Timed Petri Nets is PSPACE-complete
satisfiability	Permutation Games for the Weakly Aconjunctive mu-Calculus
scheduling	Safe and Optimal Scheduling of Hard and Soft Tasks
Security protocols	DEEPSEC: Deciding Equivalence Properties in Security Protocols Theory and Practice
segala systems	Efficient and Modular Coalgebraic Partition-Refinement
semidefinite programming	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
semigroups	Pointlike sets for varieties determined by groups
semilinear set	Weak Cost Register Automata are Still Powerful
separability	Unboundedness problems for languages of vector addition systems
separation	Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
separation problem	Pointlike sets for varieties determined by groups
series-parallel posets	Logic and rational languages of scattered and countable series-parallel posets
sets with atoms	Decidability in data Petri nets — a conjecture.
Shortest path	Graph Planning with Expected Finite Horizon
Simulation based reductions	Continuous-Time Markov Decisions based on Partial Exploration
simulation relations for timed automata	Reachability in timed automata with diagonal constraints
sp-rational languages	Logic and rational languages of scattered and countable series-parallel posets
state complexity	The Linear Space Hypothesis and Its Close Connection to Two-Way Finite Automata
stochastic games	Reachability for Branching Concurrent Stochastic Games
Strategic logics	Reasoning about Knowledge and Strategies
Strategies	Synthesizing Optimally Resilient Controllers
strategy decomposition	Solving mean-payoff parity games in pseudo-quasi-polynomial time.
Strategy Synthesis	Parity Games with Weights
structural properties	A Pattern Logic for Automata with Outputs
structures of bounded degree	An Optimal Construction for the Barthelmann-Schwentick Normal Form on Classes of Structures of Bounded Degree
sub-linear space	The Linear Space Hypothesis and Its Close Connection to Two-Way Finite Automata
Successor predicate	Uniformization Problem for Variants of First Order Logic over Words
sum-automata	A Pattern Logic for Automata with Outputs
sums-of-squares	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
Symbolic models	DEEPSEC: Deciding Equivalence Properties in Security Protocols Theory and Practice
synchronized word relations	Resynchronizing Classes of Word Relations
synthesis	Is your automaton good for playing games ?
Synthesis problem	Automatic Synthesis of Systems with Data
T
tangle learning	Solving parity games with tangles
Teaching logic	Introduction to Iltis: An Interactive, Web-Based System for Teaching Logic
Temporal logics	Reasoning about Knowledge and Strategies
the linear space hypothesis	The Linear Space Hypothesis and Its Close Connection to Two-Way Finite Automata
the subgraph isomorphism problem	On the First-Order Complexity of Subgraph Isomorphism
three-variable property	It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before"
threshold constraints	Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes
Tikz	Gralog, a visual tool for working with graphs, games, automata, logics
Time bounded reachability	Continuous-Time Markov Decisions based on Partial Exploration
timed automata	Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms Reachability in timed automata with diagonal constraints Universal Safety for Timed Petri Nets is PSPACE-complete
timed pushdown automata	Binary reachability of timed pushdown automata via quantifier elimination and cyclic order atoms
tool support	Solving parity games with tangles
Trace semantics	Bracket Algebras: a nominal theory of interleaved scopes
transducer	A new hierarchy for automaton semigroups
transducers	Regular and First Order List Functions Regular Transducer Expressions for Regular Transformations Observation synthesis for games with imperfect information Pointlike sets for varieties determined by groups A Pattern Logic for Automata with Outputs
transfinite N-free posets	Logic and rational languages of scattered and countable series-parallel posets
Transformation Monoid	Rational, Recognizable, and Aperiodic Sets in the Partially Lossy Queue Monoid
Two variables logic	Uniformization Problem for Variants of First Order Logic over Words
U
unambiguous	Regular Transducer Expressions for Regular Transformations
unambiguous automata	The Containment Problem for Unambiguous Register Automata Unambiguous languages exhaust the index hierarchy
unbounded	Expressing Unboudedness in MSO + nabla
unboundedness	Unboundedness problems for languages of vector addition systems
undecidability result	Weak Cost Register Automata are Still Powerful
Uniformization	Uniformization Problem for Variants of First Order Logic over Words
unions of conjunctive queries	Answering UCQs under updates
upper bounds	An Optimal Construction for the Barthelmann-Schwentick Normal Form on Classes of Structures of Bounded Degree
V
varieties	Pointlike sets for varieties determined by groups
vector addition system	The Reachability Problem for Vector Addition Systems is Not Elementary
vector addition systems	Unboundedness problems for languages of vector addition systems Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
Vector additions system with states	Polynomial Vector Addition Systems With States
verification	Universal parity graphs and lower bounds for parity games
visualisation	Gralog, a visual tool for working with graphs, games, automata, logics
W
weak subgame perfect equilibria	Constrained existence problem for weak subgame perfect equilibria with omega-regular Boolean objectives
weighted automata	What can you expect of a weighted automaton? Pumping lemmas for weighted automata
weighted systems	Efficient and Modular Coalgebraic Partition-Refinement
Weighted timed games	Symbolic Approximation of Weighted Timed Games
Weisfeiler-Leman algorithm	Distinguishing Graphs via Logics with Counting
well quasi orders	Decidability in data Petri nets — a conjecture.
well-structured transition systems	Regular separability of WSTS
Z
Zero-one law	Non-convergence in existential monadic second order logic of random graphs
zones	Reachability in timed automata with diagonal constraints

Disclaimer | Powered by EasyChair Smart Program