Regular Cost Functions, Part I: Logic and Algebra over Words
From MaRDI portal
Publication:2846575
DOI10.2168/LMCS-9(3:3)2013zbMath1280.03044arXiv1212.6937MaRDI QIDQ2846575
Publication date: 6 September 2013
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1212.6937
monadic second-order logicclosure operationsregular languageregular cost functionstabilization monoids
Formal languages and automata (68Q45) Undecidability and degrees of sets of sentences (03D35) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42) Word problems, etc. in computability and recursion theory (03D40)
Related Items
Trading Bounds for Memory in Games with Counters ⋮ An Approach to Computing Downward Closures ⋮ Asymptotic Monadic Second-Order Logic ⋮ Stamina: stabilisation monoids in automata theory ⋮ Cost Automata, Safe Schemes, and Downward Closures ⋮ Positive First-order Logic on Words and Graphs ⋮ Controlling a random population ⋮ A characterization of lambda-terms transforming numerals ⋮ Unnamed Item ⋮ Unboundedness Problems for Languages of Vector Addition Systems. ⋮ ω♯-Algebras ⋮ Better complexity bounds for cost register automata ⋮ Unnamed Item ⋮ A topological shuttle between inequalities and pseudoinequalities ⋮ Quantifying Bounds in Strategy Logic ⋮ Deciding Maxmin Reachability in Half-Blind Stochastic Games ⋮ The factorisation forest theorem ⋮ Better complexity bounds for cost register automata