Complexity of node coverage games

DOI10.1016/j.tcs.2015.02.002zbMath1312.68070MaRDI QIDQ2344734

Farn Wang, Sven Schewe, Jung-Hsuan Wu

Publication date: 18 May 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.02.002

zbMATH Keywords

complexity; nondeterminism; node coverage game; testing of software systems

Mathematics Subject Classification ID

91A43: Games involving graphs

91A80: Applications of game theory

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68N30: Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Shortest paths without a map
• Concurrent reachability games
• Transition graphs and the star-height of regular events
• Introduction to Software Testing
• DAG-width
• The complexity of searching a graph
• Methodology for the Generation of Program Test Data
• A genealogy of control structures
• A Complexity Measure
• Testing Software Design Modeled by Finite-State Machines
• Recontamination does not help to search a graph
• DAG-Width and Parity Games
• Automata, Languages and Programming
• The complexity of theorem-proving procedures
• Logic for Programming, Artificial Intelligence, and Reasoning