Complexity results for multi-pebble automata and their logics

DOI10.1007/3-540-58201-0_59zbMath1418.68118OpenAlexW1816348377MaRDI QIDQ4632417

Noa Globerman, David Harel

Publication date: 29 April 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58201-0_59

zbMATH Keywords

regular languagefinite automatonexponential timeregular expressioninput word

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (1)

Deterministic generalized automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on the size of sweeping automata
• Alternation with a pebble
• Complexity measures for regular expressions
• Propositional dynamic logic of regular programs
• Alternating Pushdown and Stack Automata
• Propositional dynamic logic of flowcharts
• Alternation
• Two-way automata and length-preserving homomorphisms
• State-complexity of finite-state devices, state compressibility and incompressibility

This page was built for publication: Complexity results for multi-pebble automata and their logics