Two double-exponential gaps for automata with a limited pushdown
type: Item
instance of: scholarly article
title: Two double-exponential gaps for automata with a limited pushdown
zbMATH Open document ID: 1370.68157
author: Zuzana Bednárová
author: Viliam Geffert
published in: Information and Computation
publication date: 2017-03-16T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6695649
zbMATH Keywords: pushdown automata
zbMATH Keywords: finite state automata
zbMATH Keywords: two-way automata
zbMATH Keywords: regular languages
zbMATH Keywords: descriptional complexity
MaRDI profile type: Publication
full work available at URL: j.ic.2016.06.005
OpenAlex ID: W2414151754
Wikidata QID: Q115574502
cites work: Q4198075
cites work: Q5592246
cites work: On context-free languages and push-down automata
cites work: More concise representation of regular languages by automata and regular expressions
cites work: Complexity measures for regular expressions
cites work: Language operations with regular expressions of polynomial size
cites work: NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
cites work: The Boolean closure of linear context-free languages
cites work: The state complexities of some basic operations on regular languages
cites work: The size-cost of Boolean operations on constant height deterministic pushdown automata
cites work: Boolean Language Operations on Nondeterministic Automata with a Pushdown of Constant Height
cites work: Mathematical Foundations of Computer Science 2005
cites work: Removing Nondeterminism in Constant Height Pushdown Automata
cites work: Q4506483
cites work: Q5541339
cites work: Q3455037
cites work: Nondeterminism and the size of two way finite automata
cites work: Queue Automata of Constant Length
DOI: 10.1016/J.IC.2016.06.005
description: scientific article; zbMATH DE number 6695649