Deciding path size of nondeterministic (and input-driven) pushdown automata
type: Item
instance of: scholarly article
title: Deciding path size of nondeterministic (and input-driven) pushdown automata
author: Yo-Sub Han
author: Sang-Ki Ko
author: Kai Salomaa
published in: Theoretical Computer Science
publication date: 2022-11-17T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 7619402
zbMATH Keywords: measures of nondeterminism
zbMATH Keywords: path size
zbMATH Keywords: ambiguity
zbMATH Keywords: input-driven pushdown automaton
zbMATH Keywords: decidability
MaRDI profile type: Publication
full work available at URL: j.tcs.2022.10.023
OpenAlex ID: W4307896660
cites work: Visibly pushdown languages
cites work: Adding nesting structure to words
cites work: The tractability frontier for NFA minimization
cites work: Visibly Pushdown Automata with Multiplicities: Finiteness and K-Boundedness
cites work: 2-Visibly Pushdown Automata
cites work: On the finite-valuedness problem for sequential machines
cites work: Problems on finite automata and the exponential time hypothesis
cites work: Q3323279
cites work: Q5422234
cites work: Measuring nondeterminism in pushdown automata
cites work: Edit-Distance Between Visibly Pushdown Languages
cites work: Ambiguity, Nondeterminism and State Complexity of Finite Automata
cites work: Nondeterministic state complexity of nested word automata
cites work: Q4198075
cites work: Pushdown automata with bounded nondeterminism and bounded ambiguity
cites work: Q3862379
cites work: Communication complexity method for measuring nondeterminism in finite automata
cites work: Structural properties of NFAs and growth rates of nondeterminism measures
cites work: Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
cites work: Q3890112
cites work: Q3817637
cites work: Input-Driven Pushdown Automata with Limited Nondeterminism
cites work: State complexity of operations on input-driven pushdown automata
cites work: State Complexity of Finite Tree Width NFAs
cites work: Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
cites work: Pumping and pushdown machines
cites work: Measures of nondeterminism for pushdown automata
cites work: A Second Course in Formal Languages and Automata Theory
cites work: Q3309067
cites work: On the degree of ambiguity of finite automata
cites work: Q4692941
DOI: 10.1016/J.TCS.2022.10.023
description: scientific article; zbMATH DE number 7619402